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

Ответ от Андрей Эгоист[гуру]
ссылка

Ответ от Пользователь удален[активный]
Насколько помню, это вид бесскобочной записи. Аргументы операция пишутся в стек, а операция выполняется над самыми верхними элементами стека (количество элементов зависит от вместимости/местности/арности операции).
Составляется выражение следующим образом: в конце записывается операция, выполняемая последней, а перед ней без каких-либо скобок ее аргументы в порядке, требуемом операцией. Если аргументы сами являются выражениями, то их пишут так же: наименее приоритетная операция в конце, а перед ней - ее аргументы.
Пример: выражение (4+8)*5-3*2.
Выбираем операцию, выполняемую последней, то есть последнюю операцию с наименьшим приоритетом вне скобок (это минус).
Пишем уменьшаемое, вычитаемое и знак операции:
(4+8)*5 3*2 -.
Аргументы - сами выражения. Расписываем их аналогично:
(4+8) 5 * 3 2 * -.
4 8 + 5 * 3 2 * -.
Последняя запись - результат.
Вычислять значение выражение надо в один проход, используя стек по следующей схеме: операнды заносятся в стек, а если встретилась операция, ее аргументы берутся с вершины стека и результат заносится в стек. В итоге после прохода выражения из стека вынимается значение.
ОСТАТОК ВЫРАЖЕНИЯ СТЕК
4 8 + 5 * 3 2 * -
8 + 5 * 3 2 * - 4
+ 5 * 3 2 * - 8 4
5 * 3 2 * - 12 (=4+8)
* 3 2 * - 5 12
3 2 * - 60 (=12*5)
2 * - 3 60
* - 2 3 60
- 6 (=3*2) 60
54 (=60-6)
В стеке осталось значение выражения.
Вроде все.

Ответ от 3 ответа[гуру]

Ответ от 3 ответа[гуру]