распознавание строки, содержащей мат. действия

Рекомендую почитать что-то про парсеры. Иногда в таких книжках в качестве hello world парсят как раз такую арихметику.

http://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D1%80%D1%81%D0%B8%D0%BD%D0%B3

http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%B0%D0%B...

man синтаксический анализ

читай в вики про обратную польскую запись, как раз то что тебе надо

Советую читать книжку «А. Ахо, Р. Сети, Дж. Ульман. Компиляторы. Принципы, технологии, инструменты.», а в ней главу про синтаксический анализ. Там все описано.

Обратная польская запись ?

Совершенно банально; у того же Страуструпа в книге "Язык программирования C++" рассматривается построение калькулятора для таких выражений.

В моё время первый раз эту задачу решали в школе, второй - в институте.

Неужели с тех пор так изменилась программа? :-/

http://slil.ru/27030199

.....
{
  Получение исходного (не сортированного, не связанного кода).
  Пример:
         s = '1+3-5*3^4-3'
  влечёт создание:
  (0+1), (1+3), (3-5), (5*3), (3^4), (4-3)

  Если встречаются скобки, то они выделяются и компилируются
  (и связываются)
  путём самовызова Build, их результат используется как операнд,
  а их код пристыковывается в начало компилируемого кода (Own).
  Source всегда указывает на самое начало кода.
  Пример:
         s = '2+3*(12+4)'
   (0+12), (12+4), (0+2), (2+3), (3*R)
   ^               ^                ^
  Source           Own       результат вычисления скобок (12+4)

  Кроме того, всегда создаётся нулевая инструкция с:
        op1 = nil
        operation = #0
     (Выше обозначена как (0+X))
}
.....

> В моё время первый раз эту задачу решали в школе, второй - в институте.

Да, у нас тоже на первом курсе это было как одно из практических заданий.

На flex+bison такое разбирается за 5 минут. Почитай Кернигана и Пайка "Unix Programming Evironment" у них всё разобрано.

++ за обратную польскую - она элементарна.

+пицот

Действительно обратная польская подходит, ведь знал про нее, но почему то не сообразил. Глупею...

>В моё время первый раз эту задачу решали в школе, второй - в институте.

>Неужели с тех пор так изменилась программа? :-/

Это я не для учебы, а для одной из своих "программ" делаю.Не решали таких ни в школе, ни в универе. Что-то похожее было в курсе функционального программирования, но там запись префиксная (+ 3 4), что для обработки, особенно в лиспе элементарно. Про выше сказанную обратную польскую знал, но не смекнул.

s/сказанную/упомянутую

>На flex+bison такое разбирается за 5 минут.

Такое разбирается даже на Бейсике за 10 минут.

>> В моё время первый раз эту задачу решали в школе, второй - в институте.

> Да, у нас тоже на первом курсе это было как одно из практических заданий.

И у нас

> Такое разбирается даже на Бейсике за 10 минут.

Ой, да ладно. Щас посади тебя на си это разбирать - не меньше часа чтоб до ума довести.

Не знаю как там про бейсик и флекс+бизон.

>Щас посади тебя на си это разбирать - не меньше часа чтоб до ума довести.

На Си - да. Там строки не динамические :)

А на Бейсике, пусть не за 10, но за 20 минут - точно написать можно. А что гипербола небольшая, так и на упомянутых Бизонах оно тоже не 5 минут пишется ;)

Кстати, я тут подумал (полезно как оказалось иногда бывает) и догадался как можно сделать разбиение на дерево. При этом ссылки про синтаксический анализ и алгоритмы парсинга не читал, хотел сам додуматься. Как оказалось таки додумался. Странно даже, что не додумался раньше, в последнее время я совсем отупел=(. Теперь уже прочту эти ссылки ради интереса и развития. Всем спасибо.

Дерево - это когда ресурсов девать некуда.

Классика жанра - это стеки. Парсишь строку и распихиваешь операнды в стек операндов, операции, в зависимости от приоритета, или сразу, или в стек операторов.

>Дерево - это когда ресурсов девать некуда.

Дерево оправдано когда надо вычислять много раз.

Чем в этом случае дерево лучше стека? Там тоже выражение можно отпарсить только один раз, переведя его в польскую запись.

Вот тебе вариант на прологе, на других языках удобно похожим образом (через грамматики), иначе руками рискуешь замучаться парсить )

%
% helpful
%

integer(I) -->
        digit(D0),
        digits(D),
        { number_chars(I, [D0|D])
        }.

digits([D|T]) -->
        digit(D), !,
        digits(T).
digits([]) -->
        [].

digit(D) -->
        [D],
        { code_type(D, digit)
        }.

%
% lexer
%

lex([H | T]) -->
	lexem(H), !,
	lex(T).

lex([]) --> 
	[].

lexem(N) --> integer(N).
lexem(open) --> "(".
lexem(close) --> ")".
lexem(+) --> "+".
lexem(-) --> "-".
lexem(*) --> "*".
lexem(/) --> "/".

%
% parser
%

/*
 <expr> --> <term> ( '+' <term> | '-' <term> )*
 <term> --> <factor> ( '*'  <factor> | '/'  <factor> )*
 <factor> --> <prime> | '(' <expr> ')' | '-' <factor> | '+' <factor>
 <prime> --> ( '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' )+
*/

add_all(T1, [op_term(Op, T2)| T], R) :-
	T3 =.. [Op, T1, T2],
	add_all(T3, T, R).
add_all(R, [], R).

expr(E) --> term(T1), plus_minus_terms(Terms), {add_all(T1, Terms, E)}.

plus_minus_terms([op_term(Op, T1) | T]) --> plus_minus(Op), term(T1), plus_minus_terms(T), !.
plus_minus_terms([]) --> [].

plus_minus(+) --> [+].
plus_minus(-) --> [-].

term(T) --> factor(F1), mul_div_factors(Factors), {add_all(F1, Factors, T)}.

mul_div_factors([op_term(Op, F1) | T]) --> mul_div(Op), factor(F1), mul_div_factors(T), !.
mul_div_factors([]) --> [].

mul_div(*) --> [*].
mul_div(/) --> [/].

factor(E) --> [open], expr(E), [close], !.
factor(N) --> [N], {number(N)}, !.
factor(I) --> [I], {atom(I)}.


parse(Str, Expr) :-
	phrase(lex(Lexems), Str),
	phrase(expr(Expr), Lexems).


% запускаем:
?- parse("1+(1+2)*2+4",E), Res is E.
E = 1+ (1+2)*2+4,
Res = 11 .