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

Материал из Algocode wiki
Версия от 14:18, 18 октября 2019; Глеб (обсуждение | вклад) (Новая страница: «Стек также часто используют для вычислений в каком-нибудь сложном порядке. Например, инт...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Стек также часто используют для вычислений в каком-нибудь сложном порядке. Например, интересно, как именно компьютер вычисляет выражение $(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]$

То, что осталось в конце в стеке - это и есть результат.