Expression Trees - Musings pageCMIS 240Notes on Expression Trees By Nicholas Duchon (copyright) |
And you can at least check your work with tool I wrote: |
And here's a simpler version, from Stallings:
// input: infix expression, tokenized
// data structure: temporary stack of operators
// output: postfix expression
// TOS = abbreviation for top of stack, the result of peek()
while there are more tokens
if token is "("
push token onto stack
else if token is ")"
while ((v = pop stack) != "(")
output v
else if token is operator
while stack not empty AND TOS != "(" AND priority of operator <= priority of TOS operator
output pop stack
push operator
else
output token // assume token is a variable or number
end while there are more tokens
while stack not empty
output pop stack
end while there are more items on the stack
Token |
TOS |
||
a |
a |
||
b |
b |
a |
|
+ |
a+b |
||
c |
c |
a+b |
|
d |
d |
c |
a+b |
* |
c*d |
a+b |
|
- |
(a+b)-(c*d) |
Token |
TOS |
|||
a |
a |
|||
b |
b |
a |
||
+ |
a+b |
|||
c |
c |
a+b |
||
d |
d |
c |
a+b |
|
+ |
c+d |
a+b |
||
/ |
(a+b)/(c+d) |
|||
e |
e |
(a+b)/(c+d) | ||
f |
f |
e |
(a+b)/(c+d) | |
- |
e-f |
(a+b)/(c+d) | ||
g |
g |
e-f |
(a+b)/(c+d) | |
- |
(e-f)-g |
(a+b)/(c+d) | ||
h |
h |
(e-f)-g |
(a+b)/(c+d) | |
j |
j |
h |
(e-f)-g |
(a+b)/(c+d) |
+ |
h+j |
(e-f)-g |
(a+b)/(c+d) | |
/ |
((e-f)-g)/(h+j) |
(a+b)/(c+d) | ||
+ |
(a+b)/(c+d)+((e-f)-g)/(h+j) |
Token |
TOS |
||||||
+ |
+ |
||||||
/ |
/ |
+ |
|||||
+ |
+ |
/ |
+ |
||||
a |
a |
+ |
/ |
+ |
|||
b |
b |
a |
+ |
/ |
+ |
||
(eval) |
a+b | / |
+ |
||||
+ |
+ |
a+b |
/ |
+ |
|||
c |
c |
+ |
a+b |
/ |
+ |
||
d |
d |
c |
+ | a+b |
/ |
+ |
|
(eval) |
c+d | a+b | / |
+ |
|||
(eval) |
(a+b)/(c+d) |
+ |
|||||
/ |
/ |
(a+b)/(c+d) |
+ |
||||
- |
- |
/ |
(a+b)/(c+d) | + |
|||
- |
- |
- |
/ |
(a+b)/(c+d) | + |
||
e |
e |
- |
- |
/ |
(a+b)/(c+d) | + |
|
f |
f |
e |
- |
- |
/ |
(a+b)/(c+d) | + |
(eval) |
e-f | - |
/ |
(a+b)/(c+d) | + |
||
g |
g |
e-f | - | / | (a+b)/(c+d) | + |
|
(eval) |
(e-f)-g | / |
(a+b)/(c+d) | + |
|||
+ |
+ |
(e-f)-g |
/ |
(a+b)/(c+d) | + |
||
h |
h |
+ |
(e-f)-g |
/ |
(a+b)/(c+d) | + |
|
j |
j |
h |
+ |
(e-f)-g | / | (a+b)/(c+d) | + |
(eval) |
h+j | (e-f)-g |
/ |
(a+b)/(c+d) | + |
||
(eval) |
((e-f)-g)/(h+j) |
(a+b)/(c+d) | + |
||||
(eval) |
(a+b)/(c+d)+((e-f)-g)/(h+j) |