ReversePolish

ReversePolish, commonly referred to as Reverse Polish notation (RPN) or postfix notation, is a mathematical notation in which operators follow their operands rather than appear between them. This ordering allows expressions to be evaluated by a stack machine, often without requiring parentheses.

The concept originated with the Polish logician Jan Łukasiewicz in the 1920s as part of his work on Polish notation for logic; the postfix form later gained prominence in computing and is widely used in stack-based calculators and languages such as Forth and PostScript.

Evaluation of an RPN expression uses a stack. To compute, scan tokens left to right: if the token is a number, push it onto the stack; if it is an operator, pop the required number of operands, apply the operator, and push the result back on the stack. This continues until the expression is exhausted, and the final value is on the stack.

Example: 3 4 + evaluates to 7. Another example: 5 1 2 + 4 * + 3 - evaluates to 14.

Advantages of ReversePolish notation include simplified parsing and evaluation, especially on stack machines and calculators. It is used by many devices and languages, notably HP calculators, Forth, and PostScript. Limitations include its non-intuitive nature for those accustomed to infix notation and the need for conversion when interoperating with standard mathematical text. Infix expressions can be converted to postfix with algorithms such as the shunting-yard algorithm, facilitating translation between notations. Many calculators accept RPN input directly, underscoring its practicality in certain computational contexts.