История:

Обратная польская запись была предложена Берксом, Уорреном и Райтом в 1954 году и названа так потому, что она была просто обратной польской записи (префиксной записи), изобретенной польским логиком Яном Лукасевичем, в которой оператор ставится перед операндами. В 1960-х годах он был затем независимо заново изобретен Э. В. Дейкстрой и Ф. Л. Bauer за сокращение количества обращений к компьютерной памяти и повышение производительности. Он использовал стек компьютера для хранения своих операндов перед выполнением оператора.

Определение:

Обратная польская нотация (RPN) — это метод передачи математических выражений без использования разделителей, таких как квадратные и круглые скобки. В этой нотации операторы следуют за своими операндами, что устраняет необходимость в квадратных скобках для определения приоритета оценки. Операция читается слева направо, но выполнение выполняется каждый раз при достижении оператора и всегда с использованием двух последних чисел в качестве операндов. Эта нотация подходит для компьютеров и калькуляторов, поскольку требуется отслеживать меньше символов и выполнять меньше операций.

Обратное польское обозначение также известно как постфиксное обозначение.

Способ:

RPN приводит к более быстрым вычислениям по нескольким причинам. Во-первых, меньше информации для хранения. Следовательно, вместо того, чтобы хранить девять символов для выражения ((5–3) * 2), компьютерам, использующим RPN, нужно хранить только пять символов для выражения 5 3–2 *. А поскольку для обработки требуется меньше символов, выполнение становится быстрее.

Итак, в компьютере, использующем RPN, вычисление выражения 5 1–3 * выглядит следующим образом:

  1. Вставьте 5 в стек. Это первое значение.
  2. Поместите 1 в стек. Это второе значение, и оно находится на позиции выше 5.
  3. Примените операцию вычитания, взяв из стека два операнда (1 и 5). Верхнее значение (1) вычитается из значения под ним (5), а результат (4) сохраняется обратно в стек. 4 теперь единственное значение в стеке и находится внизу.
  4. Вставьте 3 в стек. Это значение находится в позиции выше 4 в стеке.
  5. Примените операцию умножения, взяв два последних числа из стека и перемножив их. Затем результат помещается обратно в стек. После этой операции стек теперь содержит только число 12.

Инфиксное выражение ((15 ÷ (7 - (1 + 1))) × 3) - (2 + (1 + 1)) можно записать в обратной польской записи следующим образом:

15 7 1 1 + − ÷ 3 × 2 1 1 + + −

  • Вычисление этого постфиксного выражения с помощью приведенного выше алгоритма слева направо дает результат (красные элементы — это содержимое стека, полужирный — текущий токен):
15 7 1 1 + − ÷ 3 × 2 1 1 + + − =
15 7 1 1 + − ÷ 3 × 2 1 1 + + − =
15 7 1 1 + − ÷ 3 × 2 1 1 + + − =
15 7 1 1 + − ÷ 3 × 2 1 1 + + − =
15 7 1 1 + − ÷ 3 × 2 1 1 + + − =
15 7     2 − ÷ 3 × 2 1 1 + + − =
15         5 ÷ 3 × 2 1 1 + + − =
             3 3 × 2 1 1 + + − =
             3 3 × 2 1 1 + + − =
                 9 2 1 1 + + − =
                 9 2 1 1 + + − =
                 9 2 1 1 + + − =
                 9 2 1 1 + + − =
                 9 2     2 + − =
                 9         4 − =
                             5 =
                             5
  • Вычисление этого постфиксного выражения с помощью приведенного выше алгоритма справа налево дает:
15 7 1 1 + − ÷ 3 × 2 1 1 + + − =
15 7 1 1 + − ÷ 3 × 2     2 + − =
15 7 1 1 + − ÷ 3 ×         4 − =
15 7     2 − ÷ 3 ×         4 − =
15         5 ÷ 3 ×         4 − =
             3 3 ×         4 − =
                 9         4 − =
                             5

Обратная польская нотация — это способ выражения арифметических выражений, который позволяет избежать использования скобок для определения приоритетов при вычислении операторов. В обычных обозначениях можно было бы написать

(3 + 5) * (7–2)

а скобки говорят нам, что мы должны прибавить 3 к 5, затем вычесть 2 из 7 и умножить два результата вместе. В RPN номера и операторы перечислены один за другим, и оператор всегда действует на самые последние номера в списке. Числа можно представить себе как образующие стопку, как стопку тарелок. Самое последнее число помещается на вершину стека. Оператор берет соответствующее количество аргументов с вершины стека и заменяет их результатом операции.

Следующий пример:

В этих обозначениях приведенное выше выражение будет

3 5 + 7 2 — *

Если читать слева направо, это интерпретируется следующим образом:

  • Вставьте 3 в стек.
  • Вставьте 5 в стек. Если читать сверху, стек теперь содержит (5, 3).
  • Примените операцию +: возьмите два верхних числа из стека, сложите их вместе и поместите результат обратно в стек. Теперь стек содержит только число 8.
  • Поместите 7 в стек.
  • Вставьте 2 в стек. Теперь он содержит (2, 7, 8).
  • Примените операцию —: возьмите два верхних числа из стека, вычтите верхнее из нижнего и поместите результат обратно в стек. Стек теперь содержит (5, 8).
  • Примените операцию *: возьмите два верхних числа из стека, перемножьте их и поместите результат обратно в стек. Теперь стек содержит только число 40.

Спасибо