Обратная польская запись
В обратной польской записи (reverse polish notation, RPN, «постфиксная запись») знаки операций следуют после операндов, а не между ними (такая запись, то есть привычный нам со школы вид арифметических выражений, называется ещё инфиксной записью).
1 + 2 превращается в 1 2 +.
1 + 2 * 3 превращается в 1 2 3 * +.
Вычисление выражений в постфиксной записи можно провести с помощью простого стекового автомата. Такие вычисления занимают мало дополнительной, а вычислительный алгоритм простой в понимании и реализации.
Выражения в постфиксной записи не содержат скобок и не требуют учёта приоритетов операций. Поэтому превращение инфиксного выражения в постфиксное (например, с помощью алгоритма сортировочной горки), фактически, является вариантом парсинга.
Первый компактный научный калькулятор HP-35 требовал использования RPN для ввода выражений.
Данные о том, проще ли человеку выучить 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 используется для записи выражений в исходном коде. Такие языки иногда называют «стековыми».