Вычисление выражения, представленного в ПОЛИЗ
Вычисление выражения, представленного обратной польской записью, выполняется за один проход слева направо. Операнды сначала помещаются в стек. Когда встречается символ операции, то она выполняется над операндами, находящимися на вершине стека. После выполнения операции, её операнды заменяются в стеке результатом операции. В качестве примера рассмотрим выражение в польской записи .
Входной символ | Стек | Примечание |
A | A4 | |
* | R0 | R0=4*A |
2R0 | ||
X | X2R0 | |
/ | R1R0 | R1=2*X |
- | R0 | R0=R0-R1 |
3R0 | ||
B | B3R0 | |
* | R1R0 | R1=3*B |
2R1R0 | ||
Y | Y2R1R0 | |
* | R2R1R0 | R2=2xY |
+ | R1R0 | R1=R1+R2 |
* | R0 | R0=R0*R1 |
Результат получен в единственном оставшемся элементе стека.
Контрольные вопросы
1) Какие объекты помещаются в программный стек при входе в функцию?
2) Как изменяется указатель программного стека при выходе из функции?
3) Что происходит с программным стеком при рекурсивном обращении функции к самой себе?
4) Напишите обратную польскую запись для выражения
5) Напишите последовательность операций и состояние стека в процессе вычисления значения выражения, представленного польской записью из предыдущего примера.