Вычисление постфиксной записи выражения можно представить следующим
образом.
1. Просматриваем выражение слева направо пока не найдем два стоящих
рядом операнда, за
которыми следует знак операции.
2. Выполняем операцию и записываем результат вместо выбранных
операндов и операций.
3. Повторяем пункт (1) пока не получим вместо выражения единственный
результат.
Вычисление построенного постфиксного выражения можно представить в
следующем виде:
На практике вычисление постфиксных выражений реализуется с применением
магазина. В этом случае вычисления выполняются по следующим правилам.
1. Прочитать очередной символ входной цепочки.
2. Если входной символ - операнд, то выполнить его запись
в магазин.
3. Если входной символ - оператор,то прочитать два операнда из
магазина, выполнить
операцию и результат занести в магазин
как операнд.
4. Повторять п.1, пока во входной цепочке не будут прочитаны
все символы.
Последовательность вычислений продемонстрируем на примере входной цепочки
ab+cd-*
и изобразим ее в виде следующей схемы:
ab+cd-*
1. b+cd-*
a
2. +cd-*
ab
3. cd-*
R1
a+b=R1
4. d-*
R1c
5. -*
R1cd
6. *
R1R2
c-d = R2
7. $
R3
R1*R2 = R3