Entry
Datastructure: Stack: Expression: Postfix: Evaluate: How do you evaluate an RPN expression?
Jan 4th, 2004 09:56
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 28 October 2003 - 09:30 am --------------------
Datastructure: Stack: Expression: Postfix: Evaluate: How do you
evaluate an RPN expression?
---
To evaluate an expression represented in postfix, scan this expression
from left to right.
---
Steps: Overview:
1. -Create a stack for the operands
2. -While not at the end of the expression
1. read the next token from the expression
2. if this token is an operand
then push its value on this operand stack
3. if this token is a unary operator
1. pop the latest 1 operand from the
operand stack
2. evaluate this 1 operand using that
operator
3. push the result back on the stack
4. if this token is a binary operator
1. pop the latest 2 operands from the
operand stack
1. pop the first operand from the
stack
2. pop the second operand from the
stack
2. evaluate this 2 operands using that
operator
3. push the result back on the stack
3. -Endwhile: Go back to step 2.
4. -As a result, the top element of the stack
is the value of the expression
---
---
For example:
---
evaluate infix expression 3 + 4 * 5 + 6 - 7
converted to postfix, this becomes
3 4 5 * + 6 + 7 -
---
---
Note:
As a double check, after a conversion of
infix to postfix, the ORDER of the operands
should NOT CHANGE.
e.g. you see 3 4 5 6 7 in this order in the
infix expression, but then as an extra check
you should see the SAME order in the postfix
expression, that is, also 3 4 5 6 7.
If not, then something went wrong during
your conversion.
---
---
So this is the given reverse polish, or
postfix expression:
expression
+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 5 | * | + | 6 | + | 7 | - |
+---+---+---+---+---+---+---+---+---+
Evaluate this expression from left to right.
---
And this is the operand stack.
operand stack
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
First take off the first token.
That is a 3.
As 3 is an operand. Push this on the operand stack.
expression
+---+---+---+---+---+---+---+---+---+
| | 4 | 5 | * | + | 6 | + | 7 | - |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| 3 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
That is a 4.
As 4 is an operand. Push this on the operand stack.
expression
+---+---+---+---+---+---+---+---+---+
| | | 5 | * | + | 6 | + | 7 | - |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| 4 | 3 | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
That is a 5.
As 5 is an operand. Push this on the operand stack.
expression
+---+---+---+---+---+---+---+---+---+
| | | | * | + | 6 | + | 7 | - |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| 5 | 4 | 3 | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
That is a '*'
expression
+---+---+---+---+---+---+---+---+---+
| | | | | + | 6 | + | 7 | - |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| 5 | 4 | 3 | | | | | | |
+---+---+---+---+---+---+---+---+---+
As '*' is a binary operator, pop
the last 2 operands from the operand
stack, and calculate its result using
the operator.
expression
+---+---+---+---+---+---+---+---+---+
| | | | | + | 6 | + | 7 | - |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| 3 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
That gives the 2 operands 5 and 4.
Apply the operator '*' on it.
4 * 5 = 20.
Put this result back on the stack.
expression
+---+---+---+---+---+---+---+---+---+
| | | | | + | 6 | + | 7 | - |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
|20 | 3 | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | 6 | + | 7 | - |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
|20 | 3 | | | | | | | |
+---+---+---+---+---+---+---+---+---+
That is a '+'
As '+' is a binary operator, pop
the last 2 operands from the operand
stack, and calculate its result using
the operator.
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | 6 | + | 7 | - |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
That gives the 2 operands 20 and 3.
Apply the operator '+' on it.
3 + 20 = 23.
Put this result back on the stack.
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | 6 | + | 7 | - |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
|23 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | + | 7 | - |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
|23 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
That is a '6'
As 6 is an operand. Push this on the operand stack.
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | + | 7 | - |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| 6 |23 | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | | 7 | - |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| 6 |23 | | | | | | | |
+---+---+---+---+---+---+---+---+---+
That is a '+'
As '+' is a binary operator, pop
the last 2 operands from the operand
stack, and calculate its result using
the operator.
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | | 7 | - |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
That gives the 2 operands 6 and 23.
Apply the operator '+' on it.
23 + 6 = 29.
Put this result back on the stack.
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | | 7 | - |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
|29 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | - |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
|29 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
That is a '7'
As 7 is an operand. Push this on the operand stack.
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | - |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| 7 |29 | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
|7 |29 | | | | | | | |
+---+---+---+---+---+---+---+---+---+
That is a '-'
As '-' is a binary operator (in this case), pop the last 2 operands
from the operand stack, and calculate its result using the operator.
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
That gives the 2 operands 7 and 29.
Apply the operator '-' on it.
29 - 7 = 22.
Put this result back on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
|22 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
As the expression, the top element of the
stack is the value of the expression.
That is 22.
---
---
[book: source: Hubbard, John R. - Data Structures with C++ - p. 208 -
'Evaluating an expression from its postfix representation' -
http://www.amazon.com/exec/obidos/tg/detail/-
/0071353453/qid=1067330317/sr=1-1/ref=sr_1_1/103-2842924-9105401?
v=glance&s=books
---
---
Internet: see also:
---
Algorithm: Expression: Infix: Convert: Postfix: Overview: How convert
infix to postfix expression?
http://www.faqts.com/knowledge_base/view.phtml/aid/26071/fid/585
----------------------------------------------------------------------
