|
Infix expression : (In the expression, each
binary operator sits between itsoperands)
Any expression in the standard
form like 2 * 3 – 4 / 5 is an infix expression.
Postfix expression : (In the expression, each
binary operator sits immediately after the its operands)
The postfix form of the above
expression is 2 3 * 4 5 / -.
How to evaluate a postfix expression:
The algorithm for evaluating a postfix expression (as a token vector):
- Initialize
an empty stack.
- Scan the
postfix token vector from left
to right token by token.
- If the
scanned token is an operand, evaluate its value and push the value to
the top of the
stack.
- If the
scanned token is a binary operator
operator, there
will be at least two operands in the stack.
- Store the
top most element of the stack(
topStack) in a
variable operand2.
- Pop the
stack.
- Store the
top most element of the stack(
topStack) in a
variable operand1.
- Pop the
stack.
- Now
evaluate (
operand1
operator
operand2). Push the
result into the stack.
- If the
scanned token is a unary operator
operator, there
will be at least two operands in the stack.
- Store the
top most element of the stack(
topStack) in a
variable operand.
- Pop the
stack.
- Now
evaluate (
operator operand). Push the result into the
stack.
- After all tokens
are scanned, we will have only one value left in the stack. Return that
value as the result.
Example
:
Let us see how the above algorithm will be implemented using an example.
Postfix token vector : 1 2
3 * +
4 -
Initially the Stack is empty. Now, the first three tokens scanned are 1,2 and 3, which are operands. Thus they will be pushed
into the stack in that order.
|
Stack
|
Expression
|
Next token scanned is "*", which is an operator. Thus, we pop the
top two elements from the stack and perform the "*" operation with
the two operands. The second operand will be the first element that is
popped.
|
Stack
|
Expression
|
The value of the expression(2*3) that has been
evaluated(6) is pushed into the stack.
|
Stack
|
Expression
|
Next token scanned is "+", which is an operator. Thus, we pop the
top two elements from the stack and perform the "+" operation with
the two operands. The second operand will be the first element that is
popped.
|
Stack
|
Expression
|
The value of the expression(1+6) that has been
evaluated(7) is pushed into the stack.
|
Stack
|
Expression
|
Next token scanned is "4", which is added to the stack.
|
Stack
|
Expression
|
Next token scanned is "-", which is an operator. Thus, we pop the
top two elements from the stack and perform the "-" operation with
the two operands. The second operand will be the first element that is
popped.
|
Stack
|
Expression
|
The value of the expression(7-4) that has been
evaluated(3) is pushed into the stack.
|
Stack
|
Expression
|
Now, since all the tokens are scanned, the remaining element in the stack
(there will be only one element in the stack) will be returned.
End result :
- Postfix
expressions : 123*+4-
- Result : 3
|