Reverse Polish Notation Practical Implications Example

As a user interface for calculation the notation was first used in Hewlett-Packard's desktop calculators from the late 1960s and then in the HP-35 handheld scientific calculator launched in 1972. In RPN the operands precede the operator, thus dispensing with the need for parentheses. For example, the expression 3 * ( 4 + 7) would be written as 3 4 7 + *, and done on an RPN calculator as "3", "Enter", "4", "Enter", "7", "+", "*".

Implementations of RPN are stack-based; that is, operands are popped from a stack, and calculation results are pushed back onto it. Although this concept may seem obscure at first, RPN has the advantage of being extremely easy, and therefore fast, for a computer to analyze due to it being a regular grammarIn computer science a right regular grammar is a formal grammar N Σ, P S such that all the production rules in P are of one of the following forms: # A → a where A a non-terminal in N and a a terminal in Σ # A → aB where A and B in N.

1 Practical implications

2 Example

The expression is evaluated in the following way (the Stack is displayed after Operation has taken place):

The final result, 15, lies on the top of the stack at the end of the calculation.

An alternate way of viewing the stack during the above operation is shown below (as seen on HP48S calculator).

Input	Stack	Operation
1	1	Push operand
2	1, 2	Push operand
+	3	Addition
4	3, 4	Push operand
*	12	Multiplication
3	12, 3	Push operand
+	15	Addition

The enters are in brackets because they are optional when proceded by an operator press. An enter is only needed to clear the insertion mark from the line. Thus, RPN allows the expression to be entered and evaluated in eight rather than eleven or twelve steps.

3 Converting from infix notation

Like the evaluation of RPN, conversion from infix notationInfix notation is the arithmetic formula notation known to most people, in which operators are written infix-style between the operands they act on. It is not as simple to parse by computer as postfix notation, but many programming languages use it to tak to RPN is stack-based. Infix expressions are the form of math most people are used to, for instance 3+4 or 3+4*(2-1). For the conversion there are 2 text variableIn computer science and mathematics, a variable is a symbol denoting a quantity or symbolic representation. In mathematics, a variable often represents an unknown quantity; in computer science, it represents a place where a quantity can be stored. Variabls ( stringGenerally, string is a thin piece of fiber which is used to tie, bind, or hang other objects. String can be made from a variety of fibres. You can get different kinds, twine for example. The term has more specific meanings, within certain academic discipls), the input and the output. There is also a stack holding operators not yet added to the output stack. To convert, the program reads each letter in order and does something based on that letter.

3.1 A simple conversion

Input: 3+4 #Add 3 to the output stack (whenever a number is read it is added to the output) #Add 4 to the output stack # Push + (or its ID) onto the operator stack #After reading expression pop the operators off the stack and add them to the output. # In this case there is only one, "+". #Output 3 4 +

This already shows a couple of rules:

All numbers are added to the output when they are read.
At the end of reading the expression, pop all operators off the stack and onto the output.

3.2 The algorithm in detail

While there are tokens to be read:

Read a token.

If the token is a number, then add it to the output.
If the token is an operator, o₁, then:

1) while there is an operator, o₂, at the top of the stack, and either

o₁ is left-associative and its precedence is less than or equal to that of o₂, or

o₁ is right-associative and its precedence is less than that of o₂,

pop o₂ off the stack, onto the output;

2) push o₁ onto the stack.

If the token is a left parenthesis, then push it onto the stack.
If the token is a right parenthesis, then pop operators off the stack, onto the output, until the token at the top of the stack is a left parenthesis, at which point it is popped off the stack but not added to the output. If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.

When there are no more tokens to read, pop all the tokens, if any, off the stack, add each to the output as it is popped out and exit. (These must only be operators; if a left parenthesis is popped, then there are mismatched parentheses.)

3.3 Complex example

Input 3+4*2/(1-5)^2 Read "3" Add "3" to the output Output: 3 Read "+" Push "+" onto the stack Output: 3 Stack: + Read "4" Add "4" to the output Output: 3 4 Stack: + Read "*" Push "*" onto the stack Output: 3 4 Stack: + * Read "2" Add "2" to the output Output: 3 4 2 Stack: + * Read "/" Pop "*" off stack and add it to output, push "/" onto the stack Output: 3 4 2 * Stack: + / Read "(" Push "(" onto the stack Output: 3 4 2 * Stack: + / ( Read "1" Add "1" to output Output: 3 4 2 * 1 Stack: + / ( Read "-" Push "-" onto the stack Output: 3 4 2 * 1 Stack: + / ( - Read "5" Add "5" to output Output: 3 4 2 * 1 5 Stack: + / ( - Read ")" Pop "-" off stack and add it to the output, pop ( Output: 3 4 2 * 1 5 - Stack: + / Read "^" Push "^" onto stack Output: 3 4 2 * 1 5 - Stack: + / ^ Read "2" Add "2" to output Output: 3 4 2 * 1 5 - 2 Stack: + / ^ End of Expression Pop stack to output Output: 3 4 2 * 1 5 - 2 ^ / +

If you were writing an interpreter, this output would be tokenized and written to a compiled file to be later interpreted. Conversion from Infix to RPN can also allow for easier computer simplification of expressions. To do this, act like you are solving the RPN expression, however, whenever you come to a variable its value is null, and whenever an operator has a null value, it and its parameters are written to the output (this is a simplification, problems arise when the parameters are operators). When an operator has no null parameters its value can simply be written to the output. This method obviously doesn't include all the simplifications possible.

4 Real-world RPN use

Forth programming language
Hewlett-Packard science/engineering calculators
PostScript page description language
TI-68k ( TI-89) implementation
Unix system calculator program dc
Writing an Interpreter
Interactive JavaScript calculator with RPN

5 See also

6 External links

RPN or DAL? A brief analysis of Reverse Polish Notation against Direct Algebraic Logic – By James Redin
Postfix Notation Mini-Lecture – By Bob Brown

Calculators Mathematical notation

<Hide>

Home > Reverse Polish notation