Главная / ПрограммированиеСоздаём язык программирования → Лекция Я2. Обратная польская запись (RPN)

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

В обратной польской записи (reverse polish notation, RPN, «постфиксная запись») знаки операций следуют после операндов, а не между ними (такая запись, то есть привычный нам со школы вид арифметических выражений, называется ещё инфиксной записью).

1 + 2 превращается в 1 2 +.

1 + 2 * 3 превращается в 1 2 3 * +.

Вычисление выражений в постфиксной записи можно провести с помощью простого стекового автомата. Такие вычисления занимают мало дополнительной, а вычислительный алгоритм простой в понимании и реализации.

Выражения в постфиксной записи не содержат скобок и не требуют учёта приоритетов операций. Поэтому превращение инфиксного выражения в постфиксное (например, с помощью алгоритма сортировочной горки), фактически, является вариантом парсинга.

Первый компактный научный калькулятор HP-35 требовал использования RPN для ввода выражений.

Hp 35

Калькулятор HP-35

Данные о том, проще ли человеку выучить RPN или обычную инфиксную запись, противоречивые. На наш взгляд, человеку всё же удобней инфиксная запись, поскольку она опирается на то же «аппаратное обеспечение», что используется в понимании языка.

Формальная грамматика RPN

В BNF можно следующим образом определить RPN с четырьмя основными арифметическими операциями:

<expression> ::=
  number
  | <expression> <expression> <operator>

<operator> ::= "+" | "-" | "*" | "/"

Стоит обратить внимание на то, что в RPN унарные операции (если они используются) обозначаются отдельными символами. Например, унарный минус можно обозначить как 'n'.

В противном случае невозможно отличить бинарный оператор от одноимённого унарного: 3 5 - + это +(3 - 5) или 3 + (-5)?

Грамматику RPN с унарным минусом n можно записать следующим образом:

<expression> ::=
  number
  | <expression> <expression> <bin_op>
  | <expression> <un_op>

<bin_op> ::= "+" | "-" | "*" | "/"
<un_op> ::= "n"

Стековые языки программирования

В некоторых языках программирования (например, Forth) RPN используется для записи выражений в исходном коде. Такие языки иногда называют «стековыми».