Entry
Algorithm: Expression: Postfix: Convert: How to convert a postfix expression to a binary tree? [RPN]
Jan 4th, 2004 09:50
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 28 October 2003 - 05:46 pm --------------------
Algorithm: Expression: Postfix: Convert: How to convert a postfix
expression to a binary tree? [RPN]
---
This method is just a special case of the postfix expression evaluation
algorithm.
---
Only in this case you do not store the operands in the stack, but
instead the binary tree pointers of the intermediate results.
So you basically work with tree pointers, instead of operands.
---
Here is the general method of evaluating a postfix 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
---
---
So just replacing some of the words here:
---
---
To evaluate an expression represented in postfix, to a binary
tree representation, scan this postfix expression
from left to right.
---
Steps: Overview:
1. -Create a stack for the binary tree pointers
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
1. create a binary tree
1. with as string that operand,
2. with a leftpointer nil,
3. and a rightpointer nil.
2. push the root of this binary tree
on the binary pointer stack
3. if this token is a unary operator
1. pop the latest 1 binary tree pointers
from the binary tree pointer stack
2. create a binary tree
1. with as string that operator,
2. with as leftpointer that binary
tree pointer
(could also be rightpointer,
that is up to you)
3. push the result back on the stack
4. if this token is a binary operator
1. pop the latest 2 binary tree pointers
from the binary tree pointer stack
2. create a binary tree
1. with as string that operator,
2. with a leftpointer the latest binary
tree pointer
3. with a rightpointer the but latest binary tree pointer
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 final binary tree representing that
postfix expression.
---
---
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
----------------------------------------------------------------------
