Обратная польская запись
Материал из Algocode wiki
Стек также часто используют для вычислений в каком-нибудь сложном порядке. Например, интересно, как именно компьютер вычисляет выражение $(1 + 2) * (100 * (3 / 2) + 3) + 4$. Его вычислять сложно, давайте перепишем его в другом формате, в котором его вычислять проще:
$[1, 2, +, 100, 3, 2, /, *, 3, +, *, 4, +]$
Такой список чисел и операций называют **обратной польской записью**. Она вычисляется так: нужно проходить слева направо и
- если встречается число - кладем его в стек
- если встречается операция - снимаем с конца стека два числа, применяем к ним эту операцию, и кладем результат в стек
Например для этого выражения стек будет вести себя так:
- []
- $[1]$
- $[1, 2]$
- $[3]$
- $[3, 100]$
- $[3, 100, 3]$
- $[3, 100, 3, 2]$
- $[3, 100, 1.5]$
- $[3, 150]$
- $[3, 150, 3]$
- $[3, 153]$
- $[459]$
- $[459, 4]$
- $[463]$
То, что осталось в конце в стеке - это и есть результат.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin