Entry
Algorithm:Expression:Infix:Convert:Postfix:How convert infix to postfix expression? No bracket [RPN]
Jan 4th, 2004 09:48
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 28 October 2003 - 11:47 am --------------------
Algorithm:Expression:Infix:Convert:Postfix:How convert infix to
postfix expression? No bracket [RPN]
---
Steps: Overview:
---
1. If your expression does contain NO brackets:
1. -Create yourself or find a table with the priority of the tokens:
For example, use this table:
----------------------
Token Priority
----------------------
# 0
- 1
+ 1
* 2
/ 2
a, b, c, ... 3
digits 3
----------------------
2. -Create a stack
1. Put the special token '#' on the
stack. This will serve to mark
the empty stack.
3. -While not at the end of the expression
1. read the next token from the expression
2. if this token has a GREATER PRIORITY
than the last token on the stack,
push its value on this stack
else
3. if this token has a SMALLER OR EQUAL PRIORITY
than the last token on the stack
1. remove all stack tokens
with a priority higher or equal
than that token, and put
this removed tokens at the end
of the result.
2. after that push that token on the
stack
4. -Endwhile: Go back to step 3.
5. -If the expression becomes empty, and you
are finished, remove and output all
the remaining tokens (except the special
'#' token) from the stack.
Put these tokens at the end of the result.
---
---
For example:
---
Convert the infix expression 3 + 4 * 5 + 6 - 7
to a postfix expression.
You should after this have a result of:
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 infix expression:
expression
+---+---+---+---+---+---+---+---+---+
| 3 | + | 4 | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+
This is an expression without brackets.
Evaluate this expression from left to right.
---
And this is your stack.
your stack
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
And in here you store the result
your result
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
First put the special token '#' on the stack.
expression
+---+---+---+---+---+---+---+---+---+
| 3 | + | 4 | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+
| # | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
First take off the first token.
expression
+---+---+---+---+---+---+---+---+---+
| | + | 4 | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+
| # | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
That is a 3.
---
Look in your table for the priority of 3.
As this is a digit, this is 3.
Look in your table for the priority of the
current last token on the stack, that is '#'.
That is 0.
As the digit 3 has a GREATER priority than
the token '#', push 3 on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+
| | + | 4 | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| 3 | # | | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | 4 | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| 3 | # | | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
That is a '+'
---
Look in your table for the priority of '+'.
That shows to be 1.
Look in your table for the priority of the
current last token on the stack, that is '3'.
That is 3.
As the priority of the
token '+' is SMALLER than the priority of the digit '3'
(because 1 is smaller than 3),
pull this '3' off the stack
and put it in the result.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | 4 | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| # | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
As the token '+' has a GREATER priority than
the token '#', push '+' on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | 4 | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| + | # | | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
expression
+---+---+---+---+---+---+---+---+---+
| | | | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| + | # | | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
That is a '4'
---
Look in your table for the priority of '4'.
Because 4 is a digit, that is 3.
Look in your table for the priority of the
current last token on the stack, that is '+'.
That is 1.
As the priority of the token '4' is GREATER
than the priority of the token '+', push
'4' on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| 4 | + | # | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| 4 | + | # | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
That is a '*'
---
Look in your table for the priority of '*'.
That shows to be 2.
Look in your table for the priority of the
current last token on the stack, that is '4'.
That is 3.
As the priority of the
token '*' is SMALLER than the priority of the digit '4'
(because 2 is smaller than 3),
pull this '4' off the stack
and put it in the result.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| + | # | | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | 4 | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
As the token '*' has a GREATER priority than
the token '+', push '*' on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| * | + | # | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | 4 | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| * | + | # | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | 4 | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
That is a '5'
---
Look in your table for the priority of '5'.
Because 5 is a digit, that is 3.
Look in your table for the priority of the
current last token on the stack, that is '*'.
That is 2.
As the priority of the token '5' is GREATER
than the priority of the token '*', push
'5' on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| 5 | * | + | # | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | 4 | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| 5 | * | + | # | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | 4 | | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
That is a '+'
---
Look in your table for the priority of '+'.
That shows to be 1.
Look in your table for the priority of the
current last token on the stack, that is '5'.
That is 3.
As the priority of the
token '+' is SMALLER than the priority of the digit '5'
(because 1 is smaller than 3),
pull this '5' off the stack
and put it in the result.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| * | + | # | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 5 | | | | | | |
+---+---+---+---+---+---+---+---+---+
---
As the priority of the
token '+' is SMALLER than the priority of the token '*'
(because 1 is smaller than 2),
pull this '*' off the stack
and put it in the result.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| + | # | | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 5 | * | | | | | |
+---+---+---+---+---+---+---+---+---+
---
As the priority of the
token '+' is EQUAL to the priority of the token '+'
(because 1 is equal to 1)
pull this '+' off the stack
and put it in the result.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| # | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 5 | * | + | | | | |
+---+---+---+---+---+---+---+---+---+
---
As the token '+' has a GREATER priority than
the token '#', push '+' on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| + | # | | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 5 | * | + | | | | |
+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | | - | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| + | # | | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 5 | * | + | | | | |
+---+---+---+---+---+---+---+---+---+
---
That is a '6'
---
Look in your table for the priority of '6'.
Because 6 is a digit, that is 3.
Look in your table for the priority of the
current last token on the stack, that is '+'.
That is 1.
As the priority of the token '6' is GREATER
than the priority of the token '+', push
'6' on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | | - | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| 6 | + | # | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 5 | * | + | | | | |
+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| 6 | + | # | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 5 | * | + | | | | |
+---+---+---+---+---+---+---+---+---+
---
That is a '-'
---
Look in your table for the priority of '-'.
That shows to be 1.
Look in your table for the priority of the
current last token on the stack, that is '6'.
That is 3.
As the priority of the
token '-' is SMALLER than the priority of the digit '6'
(because 1 is smaller than 3),
pull this '6' off the stack
and put it in the result.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| + | # | | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 5 | * | + | 6 | | | |
+---+---+---+---+---+---+---+---+---+
---
As the priority of the
token '-' is EQUAL to the priority of the token '+'
(because 1 is equal to 1),
pull this '+' off the stack
and put it in the result.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| # | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 5 | * | + | 6 | + | | |
+---+---+---+---+---+---+---+---+---+
---
As the token '-' has a GREATER priority than
the token '#', push '-' on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | 7 |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| - | # | | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 5 | * | + | 6 | + | | |
+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| - | # | | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 5 | * | + | 6 | + | | |
+---+---+---+---+---+---+---+---+---+
---
That is a '7'
---
Look in your table for the priority of '7'.
Because 7 is a digit, that is 3.
Look in your table for the priority of the
current last token on the stack, that is '-'.
That is 1.
As the priority of the token '7' is GREATER
than the priority of the token '-', push
'7' on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| 7 | - | # | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 5 | * | + | 6 | + | | |
+---+---+---+---+---+---+---+---+---+
---
Because you have now reached the end of the expression, you have to
remove all the remaining tokens on the stack (except the '#' token),
and put them in the result.
---
expression
+---+---+---+---+---+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
operand stack
+---+---+---+---+---+---+---+---+---+
| # | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 5 | * | + | 6 | + | 7 | - |
+---+---+---+---+---+---+---+---+---+
---
Your result contains now your original infix expression converted to
postfix or reverse polish notation.
---
---
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
----------------------------------------------------------------------
