Algebraic expressions can be written using three separate but equivalent notations namely infix, postfix, and prefix notations.
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
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
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.
Add a ) at the end of the post fix expression
Scan every character of the postfix expression and repeat Steps 3 and 4 until ) is encountered
If an operand is encountered, out it on the STACK.
If an operator O is encountered, then
POP the two top elements of STACK as A(topmost element) and B(next-to-top element).
Evaluate B O A.
Push the result of evaluation on the STACK.
SET RESULT equal to the topmost element of the STACK.
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.
|3||8, 2, 3|
|8||8, 6, 8|
|2||8, 14, 2|
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.
Push "(" on to the stack, and add ")" to the end of infix expression.
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
Repeatedly pop from stack and add it to the postfix expression until a "(" is encountered.
Discard the "(" . That is, remove the "(" from stack and do not add it to the postfix expression.
IF an operator O is encountered, then
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.
Push the operator O to the stack.
Repeatedly pop from the stack and add it to the postfix expression until the stack is empty.
Convert the infix expression
A + ( B * C )
into postfix expression.
|Infix Character Scanned||Stack||Postfix Expression|
|(||( + (||A|
|B||( + (||A B|
|*||( + ( *||A B|
|C||( + ( *||A B C|
|)||A B C * +|