Reverse Polish Notation

View Code

Now that a Stack is defined what is it used for? One important use is the program stack. Everytime a function is called in a program the current memory location is pushed onto the stack. When the fucnction is ended, the returns to the position of the popped value. Also anything done in recursion can be done with a stack. Recursion is just a particular use of the program stack.

Aother main reason for a stack is to evalute reverse Polish notaion aka postfix notation. When an expression in math is written the operator can go in three posible postions of the operands, before +AB, in the middle A+B, and after AB+. These are called respectivly prefix, infix, and postfix notataion. Common math uses infix notaion but there is a draw back. With infix the order of evalutation is based on the position of parenthesis. With pre and postfix--from here in when postfix is stated prefix also applies--the positition of the operators and operands alone designate order.

With this in mind it is easier for a computer to evaluate an expression in posfix notation rather than infix. In fact the very first caculators had to recieve input in postfix notaion, and every infix expression in a modern computer is translated into postfix at some point.

The Stack comes into play since it is the tool to translated infix to postfix, and to evaluate a pre or postfix expression.

Convert Infix to Postfix Notation

  1. Write the expression so that order of operation is explicitly expressed by parenthesis and operators.
  2. Working from the innermost to the outermost parenthesis set, remove the parenthesis and place the operator where the right parenethesis was. (For prefix reaplace with left parenthesis instead.)
  3. Repeat until all the parenthesis are replaced.
Example of Converting Infix to Postfix Notation
Expression Comments
(-B+(B^2-4AC)^.5)/(2A) Half of the Quadratic Formula. (I replaced the plus or minus part with plus to simplify things.
((B^2-4*A*C)^.5 - 5)/(2*A) Every operator is explicite.
(((((B^2)-((4*A)*C))^.5)-5)/(2*A)) Order is made explicite with parenthesis.
(((( B2^ -((4*A)*C))^.5)-5)/(2*A)) The innermost group is (B^2), so replace that with B2^.
(((( B2^ -( 4A* *C))^.5)-5)/(2*A)) Next is (4*A), which is replace with 4A*.
(((( B2^ - 4A*C*)^.5)-5)/(2*A)) Now the innermost group is (4A* * C). Notice that the 4A* is treated as a group. This expression is replaced with 4A*C*, which also is treated as a group.
(((B2^4A*C*- ^ .5)-5)/(2*A)) Next comes (B2^ - 4A*C*), with B2^4A*C*-.
(( B2^4A*C*-.5^ - 5)/(2*A)) Now the square root (B2^4A*C*- ^ .5) becomes B2^4A*C*-.5^
(B2^4A*C*-.5^5- / (2*A)) After that is the minus five.
(B2^4A*C*-.5^5- / 2A*) Next is the patiently waiting (2*A).
B2^4A*C*-.5^5-2A*/ Finally the division is replaced and viola. The quadratic formula in post fix notation.

The process of evaluating and translating to postfix involves a stack. Remeber that the infx must have order expressed explicitly by parenethesis.

Infix to Postfix Using a Stack

  1. Read a character.
    1. If it is an operand output it.
    2. If it is an operator or open parenthesis push it.
    3. If it is a close parenthesis, pop stack and output contents until a open parenethesis. Do not output open parenthesis.
  3. Repeat until the expression is finished.

Evaluate Postfix Using a Stack

  1. Read a character.
    1. If it is an operand push it.
    2. If it is an operator
      1. Pop stack twice.
      2. Evaluate expression to the operands. (Pay attention to order.)
      3. Push value on stack.
  3. Repeat until the expression is finished. Value in stack is the value of the expression.

Example of Translating Infix to Post with a Stack
Stack Output Comments
NULL NULL Starting with an empty stack and the expression (((5*2)-7)/3). Since it will be read left to right parenthesis around 5*2 isn't needed. The right/top side of the table is the bottom of the stack, and operands are separated by brackets.
[(]NULLRead the first character (. Push it to the stack since it is an open parenethesis.
[(] [(]5Read 5. Since it is a number output it.
[(] [(] [*]5Next is a *, so push it.
[(] [(] [*]5 2Next is a 2, so output it.
[(] [(] 5 2 *Next is a ), so pop stack and output it until (.
[(] [(] [-]5 2 *Next is a -, so push it.
[(] [(] [-]5 2 * 7Next is a 7, so output it.
[(]5 2 * 7 -Next is a ), pop stack and output it until (.
[(] [/]5 2 * 7 -Next is a /, push it.
[(] [/]5 2 * 7 - 3Next is a 3, output it.
NULL5 2 * 7 - 3 /Final there is a ), pop stack and output it until (.

Example of Evaluating Postfix with a Stack
Stack Comments
NULLStarting with the expression 5 2 * 7 - 3 /.
[5]Read 5, push to stack.
[5] [2]Read 2, push to stack.
[10]Read *, pop off two numbers and push to stack 5*2. Notice order.
[10] [7]Read 7, push to stack.
[3]Read -, pop off tow numbers and push to stack 10-7. Notice order.
[3] [3]Read 3, push to stack.
[1]Read /, pop off two numbers and push to stack 3/3.
[1]That's it 5 2 * 7 - 3 / == 1.

Those alogorithms for conversion is already in a pseudo code form so implementing them should not be too hard. Also if you did not notice the algorithm for converting infix to postfix is gereneralized. Point 2.3 compensates if the expression did not explicitly define total order of operations with parenethesis. If every operations was given a parenthesis the every other item on the stack must be and open parenethesis.

By the way, the reason postfix is also called Reverse Polish Notation is becuase the Polish mathematician Jan Lukasiewicz (lü-käl-sha-véch) developed it. It is reverse becuase the sign goes at the end, and it is Polish becuase Lukasiewicz is too hard to say.

Prev -- Back to Portal -- Next