Polish Notation Using Stack

Polish Notation

Algebraic expressions can be written using three separate but equivalent notations namely infix, postfix, and prefix notations.

Infix Notation

The operator symbol is placed between its two operands in most arithmetic operations. This is called infix expression. For example, (A + B) ; here the operator + is placed between the two operands a and b.

Although we find it simple to write expressions in infix notation, computers find it difficult to parse. So, the computer normally evaluates arithmetic expressions written in infix notation after converting them into postfix notation. The stack is the primary tool used to complete the given task in each phase.

Prefix Notation (Polish Notation)

Computers perform better when expressions are written in prefix and postfix notations.

Prefix notation refers to the notation in which the operator is placed before its two operands. For example, if A + B is an expression in infix notation, then +AB is the equivalent expression in prefix notation.

Postfix Notation (Reverse Polish Notation)

In postfix notation, the operator is placed after the operands. For example, if an expression is written in infix notation as A + B, it can be written in postfix notation as AB+.

The evaluation of a postfix and prefix expressions are always performed from left to right.

Evaluation of a Postfix Expression

The following algorithm is used to evaluate the value of a postfix expression.

1. Add a ) at the end of the post fix expression
2. Scan every character of the postfix expression and repeat Steps 3 and 4 until ) is encountered
3. If an operand is encountered, out it on the STACK.
4. If an operator O is encountered, then
   1. POP the two top elements of STACK as A(topmost element) and B(next-to-top element).
   2. Evaluate B O A.
   3. Push the result of evaluation on the STACK.
5. SET RESULT equal to the topmost element of the STACK.

Example

Consider the following postfix notation 8 2 3 * 8 + 2 / –. The equivalent infix expression is 8 – ((2 * 3) + 8) / 2 .

The following table shows the procedure for evaluating the expression by simulating the above algorithm.

The final number in the stack, 1, is the value of the postfix expression.

Conversion of an Infix Expression into a Postfix Expression

For the sake of simplicity, we will only use the +, –, *, /, and % operators. The order of precedence of these operators is as follows:

• Higher priority *, /, %
• Lower priority +, –

The algorithm below converts an infix expression to a postfix expression.

1. Push "(" on to the stack, and add ")" to the end of infix expression.
2. Repeat until each character in the infix notation is scanned
   • IF a "(" is encountered, push it on the stack.
   • IF an operand is encountered, add it to the postfix expression.
   • IF a ")" is encountered, then
     1. Repeatedly pop from stack and add it to the postfix expression until a "(" is encountered.
     2. Discard the "(" . That is, remove the "(" from stack and do not add it to the postfix expression.
   • IF an operator O is encountered, then
     1. Repeatedly pop from stack and add each operator (popped from the stack) to the postfix expression which has the same precedence or a higher precedence than O.
     2. Push the operator O to the stack.
3. Repeatedly pop from the stack and add it to the postfix expression until the stack is empty.

Example

Convert the infix expression A + ( B * C ) into postfix expression.