Прямая польская запись и проблемы с ней...
Есть алгоритм преобразования арифметического выражения в прямую//обратную польскую запись.
А как перевести выражение из польской записи в арифметическое, соблюдая скобки?
Вот что я придумал:
просматривать строку слева направо. Если очередной символ - знак, то добавлять его в стек.
Если нет, то выводить в результирующую строку и вывлдить (если стек не пуст) знак из стека.
Например: -+a*bc/d+ab
результат [COLOR=red]стек[/COLOR]
--- [COLOR=red] -[/COLOR]
--- [COLOR=red] -,+[/COLOR]
a+ [COLOR=red] -[/COLOR]
a+ [COLOR=red] -,*[/COLOR]
a+b* [COLOR=red] -[/COLOR]
a+b*c- [COLOR=red] пусто[/COLOR]
a+b*c- [COLOR=red] /[/COLOR]
a+b*c-d/ [COLOR=red] +[/COLOR]
a+b*c-d/a+b
Работает. Только скобок не хватает:( На самам деле выражение выглядит так: a+b*c-d/(a+b)
Как можно это исправить? Заранее спасибо!
А как перевести выражение из польской записи в арифметическое, соблюдая скобки?
Вот что я придумал:
просматривать строку слева направо. Если очередной символ - знак, то добавлять его в стек.
Если нет, то выводить в результирующую строку и вывлдить (если стек не пуст) знак из стека.
Например: -+a*bc/d+ab
результат [COLOR=red]стек[/COLOR]
--- [COLOR=red] -[/COLOR]
--- [COLOR=red] -,+[/COLOR]
a+ [COLOR=red] -[/COLOR]
a+ [COLOR=red] -,*[/COLOR]
a+b* [COLOR=red] -[/COLOR]
a+b*c- [COLOR=red] пусто[/COLOR]
a+b*c- [COLOR=red] /[/COLOR]
a+b*c-d/ [COLOR=red] +[/COLOR]
a+b*c-d/a+b
Работает. Только скобок не хватает:( На самам деле выражение выглядит так: a+b*c-d/(a+b)
Как можно это исправить? Заранее спасибо!
При разборе нужно помнить правила:
слева направо;
opAB -> AopB, где op - операция, A,B - операнды;
А вот и сам процес разбора(красный - результат,[] - будем разбирать)
1: -+a[*bc]/d+ab
2: -[+a[COLOR=red](b*c)[/COLOR]]/d+ab
3: -[COLOR=red](a+(b*c))[/COLOR]/d[+ab]
4: -[COLOR=red](a+(b*c))[[/COLOR]/d[COLOR=red](a+b)[/COLOR]]
5: [-[COLOR=red](a+(b*c))[/COLOR] [COLOR=red](d/(a+b))[/COLOR]]
6: [COLOR=red](a+(b*c))-(d/(a+b))[/COLOR]
Замечание к твоему алгоритму - в стек нужно класть не только знаки(операции) но и промежуточные выражения.
А вообще поищи правила разбора - алгоритмы уже давно есть и изобретать велосипед нет смысла :)
P.S. Скобки, не имеющие смысла с точки зрения арифметики можно убрать - но это совсем другая история.
слева направо;
opAB -> AopB, где op - операция, A,B - операнды;
А вот и сам процес разбора(красный - результат,[] - будем разбирать)
1: -+a[*bc]/d+ab
2: -[+a[COLOR=red](b*c)[/COLOR]]/d+ab
3: -[COLOR=red](a+(b*c))[/COLOR]/d[+ab]
4: -[COLOR=red](a+(b*c))[[/COLOR]/d[COLOR=red](a+b)[/COLOR]]
5: [-[COLOR=red](a+(b*c))[/COLOR] [COLOR=red](d/(a+b))[/COLOR]]
6: [COLOR=red](a+(b*c))-(d/(a+b))[/COLOR]
Замечание к твоему алгоритму - в стек нужно класть не только знаки(операции) но и промежуточные выражения.
А вообще поищи правила разбора - алгоритмы уже давно есть и изобретать велосипед нет смысла :)
P.S. Скобки, не имеющие смысла с точки зрения арифметики можно убрать - но это совсем другая история.
Цитата:
Originally posted by slavko
При разборе нужно помнить правила:
слева направо;
opAB -> AopB, где op - операция, A,B - операнды;
А вот и сам процес разбора(красный - результат,[] - будем разбирать)
1: -+a[*bc]/d+ab
2: -[+a[COLOR=red](b*c)[/COLOR]]/d+ab
3: -[COLOR=red](a+(b*c))[/COLOR]/d[+ab]
4: -[COLOR=red](a+(b*c))[[/COLOR]/d[COLOR=red](a+b)[/COLOR]]
5: [-[COLOR=red](a+(b*c))[/COLOR] [COLOR=red](d/(a+b))[/COLOR]]
6: [COLOR=red](a+(b*c))-(d/(a+b))[/COLOR]
Замечание к твоему алгоритму - в стек нужно класть не только знаки(операции) но и промежуточные выражения.
А вообще поищи правила разбора - алгоритмы уже давно есть и изобретать велосипед нет смысла :)
P.S. Скобки, не имеющие смысла с точки зрения арифметики можно убрать - но это совсем другая история.
При разборе нужно помнить правила:
слева направо;
opAB -> AopB, где op - операция, A,B - операнды;
А вот и сам процес разбора(красный - результат,[] - будем разбирать)
1: -+a[*bc]/d+ab
2: -[+a[COLOR=red](b*c)[/COLOR]]/d+ab
3: -[COLOR=red](a+(b*c))[/COLOR]/d[+ab]
4: -[COLOR=red](a+(b*c))[[/COLOR]/d[COLOR=red](a+b)[/COLOR]]
5: [-[COLOR=red](a+(b*c))[/COLOR] [COLOR=red](d/(a+b))[/COLOR]]
6: [COLOR=red](a+(b*c))-(d/(a+b))[/COLOR]
Замечание к твоему алгоритму - в стек нужно класть не только знаки(операции) но и промежуточные выражения.
А вообще поищи правила разбора - алгоритмы уже давно есть и изобретать велосипед нет смысла :)
P.S. Скобки, не имеющие смысла с точки зрения арифметики можно убрать - но это совсем другая история.
Спасибо! Я понял :)