Парсер выражений методом рекурсивного спуска

[hidforce]

Здравствуйте, уважаемые форумчане! Подскажите, пожалуйста: как реализовать парсер арифметических выражений методом рекурсивного спуска? Заранее спасибо!

[Stilet]

Я так полагаю, что требуется вызывать функцию считывания элементов выражения. Если встречается скобочка эта функция вызывается рекурсивно до первой (для нее без внутренних рекурсий) скобочки.
А я зык то хоть какой?

[hidforce]

Stilet, язык С++, но я не прошу, чтоб за меня написали готовый парсер. Просто хочу, чтоб понимающие люди объяснили суть этого метода.

[Stilet]

Ну с коленки могу набросать идею:

string scaner(string s,int b){
 int i=b;
 for(;i<s.length();i++){
   if(s[i]=='(') cout<<endl<<scaner(s,i); else
   if(s[i]==')') break;
 }
 return s.substr(i,i-b);
}
...
string exp='(5*(8+7))';
cout<<endl<<scaner(exp,0);

Т.е.: Проходим рекурсивно по выражению, если встречается открывающая скобочка, и выходим с выводом в консоль - если встретилась ее закрывающая.

[Utkin]

Вкратце - каждая операция рассматривается как а операция b, причем сначала рассматриваются операции низшего приоритета.
Допустим есть выражение
3+5*(8-9*8)

1) перед нами а + b
а=3
b=5*(8-9*8)
С а все ясно, просто получим число и пес с ним.
2) b - перед нами операция a*b
a=5
b=(8-9*8)
С а все ясно, просто получим число и пес с ним.
3) b - перед нами операция a-b
a=8
b=9*8
С а все ясно, просто получим число и пес с ним.
4) b - перед нами операция a*b
a=9
b=8

[hidforce]

Спасибо! Сейчас буду разбираться.

[Utkin]

Для ускорения надо
1) Функция поиска операций в порядке от низкого приоритета к высшему (при этом скобки считаются целым операндом и поиск операций внутри скобок не производится).
2) Уметь разбирать выражение на три части a операция b
3) Уметь извлекать выражение из скобок

Вкратце этого достаточно. Унарные операции можно преобразовывать в бинарные
Например: -5 = 0 - 5, а значит перед нами выражение a - b и понеслась.

Важный момент приоритет операций:
5 + 6/9
a + b (но не a/b!) - всегда сначала рассматриваются операции с наименьшим приоритетом.

[hidforce]

Ребята, помогите еще, пожалуйста! Как мне распарсить, например, такое выражение: 5-3+1..5+7, где 1...5 - ряд чисел от 1 до 5. Надо, чтоб программа как-то распознала этот ряд и вывела на экран 5-3+ряд(1,5)+7. Как такое реализовать?

[Pavia]

А сами как думаете? Тут же просто цикл с условием.