Reverse Polish notation

infogalactic Reverse Polish notation

Reverse Polish notation (RPN) is a mathematical notation in which every operator follows all of its operands, in contrast to Polish notation (PN), which puts the operator in the prefix position. It is also known as postfix notation and is parenthesis-free as long as operator arities are fixed. The description "Polish" refers to the nationality of logician Jan Łukasiewicz,[1] who invented (prefix) Polish notation in the 1920s.

Postfix algorithm

Converting from infix notation

Main article: Shunting-yard algorithm

Edsger Dijkstra invented the shunting-yard algorithm to convert infix expressions to postfix (RPN), so named because its operation resembles that of a railroad shunting yard.

There are other ways of producing postfix expressions from infix notation. Most operator-precedence parsers can be modified to produce postfix expressions; in particular, once an abstract syntax tree has been constructed, the corresponding postfix expression is given by a simple post-order traversal of that tree.