Для вычисления выражений, записанных в постфиксной форме (обратной польской нотации), используется стек. В процессе вычисления выполняются следующие шаги:
- Читаем выражение слева направо.
- Если символ является числом, помещаем его в стек.
- Если символ является оператором, извлекаем из стека необходимое количество операндов (в случае унарного оператора — один, в случае бинарного оператора — два), выполняем операцию и результат кладем обратно в стек.
- Повторяем процесс до конца выражения.
- В конце в стеке останется один элемент — это и будет результат выражения.
Рассмотрим, как это работает на вашем примере с выражением 54321----
:
- Читаем
5
— кладем в стек. Стек: [5]
- Читаем
4
— кладем в стек. Стек: [5, 4]
- Читаем
3
— кладем в стек. Стек: [5, 4, 3]
- Читаем
2
— кладем в стек. Стек: [5, 4, 3, 2]
- Читаем
1
— кладем в стек. Стек: [5, 4, 3, 2, 1]
Теперь начинаем читать операторы -
:
- Читаем
-
— извлекаем последние два элемента из стека: 2
и 1
. Вычисляем 2 - 1 = 1
и кладем результат обратно в стек. Стек: [5, 4, 3, 1]
- Читаем
-
— извлекаем последние два элемента из стека: 3
и 1
. Вычисляем 3 - 1 = 2
и кладем результат обратно в стек. Стек: [5, 4, 2]
- Читаем
-
— извлекаем последние два элемента из стека: 4
и 2
. Вычисляем 4 - 2 = 2
и кладем результат обратно в стек. Стек: [5, 2]
- Читаем
-
— извлекаем последние два элемента из стека: 5
и 2
. Вычисляем 5 - 2 = 3
и кладем результат обратно в стек. Стек: [3]
В стеке остался один элемент, который и является результатом выражения: 3
.
Таким образом, результат вычисления выражения 54321----
равен 3
.