Entry
Algorithm:Expression:Infix: Convert: Postfix: How convert infix to postfix expression? Bracket [RPN]
Jan 4th, 2004 09:54
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 28 October 2003 - 11:47 am --------------------
Algorithm:Expression:Infix: Convert: Postfix: How convert infix to
postfix expression? Bracket [RPN]
---
Steps: Overview:
---
If your infix expression does contain brackets:
---
In the case your expression contains brackets you will need to use TWO
priority tables.
---
This is the so called Dijkstra's double priority algorithm.
---
This because the behaviour of the bracket has to be given
a different priority when it is located on the stack, versus
the case that you take that bracket off the expression.
So you can not use the same priority.
So you must use two priorities.
---
One table which you use while you take that token off the
expression. You call that table the INPUT PRIORITY TABLE.
---
And another table which you use for a token on
the stack. You call that table the STACK PRIORITY TABLE.
---
So in this 2 tables, ONLY the priority of the BRACKETS (or thus '(' and
')')will be different, for all the other tokens keep the SAME priority
in both tables.
---
---
Steps: Overview:
1. -Create yourself or find a table with the priority of the tokens:
For example, use this table, which will cover most cases.
------------------------------------
Input Stack
Token Priority Priority
table table
------------------------------------
# 0 0
- 3 3
+ 3 3
* 4 4
/ 4 4
^ 5 5
variables 9 9
digits 9 9
( 9 2
) 2 9
------------------------------------
---
---
About how this table is made (or similar tables
to be made by you e.g. for other operators like
NOT, OR, AND, '=', ...).
This numbers in this table are basically ARBITRARILY (in other words it
is up to you to choose them).
The only thing that is important is that an operator (or similarly an
operand) which has a HIGHER priority also gets a HIGHER number
assigned. And thus equivalently, the LOWER the priority the LOWER the
number.
And if the priority is the SAME they get the SAME number.
So you see e.g. in the table that as in algebra
the '^' has a higher priority (or thus a higher number 5)
than the '*' (or thus number 4), and higher than
the '+' (or thus number 3).
In general thus the higher the priority, the higher
the number you assign it.
Or vice versa the lower the priority, the lower the
number you assign it.
Or also if the same priority, the same number.
So like 3,
or thus the same both for for '+' and '-',
and
similar 4, or
thus also the same for '*' and '/'
when it is given or wanted that they
have both EQUAL priority.
So you could e.g. multiply all numbers in the table
abouve by 10 or by 100 or by 1000, ... and so on.
(which might be a good idea and come handy if you want to add new
operators in between in the list, as it basically stretches
the 'distance' in between the numbers from 1 to 10 and so on, so some
extra operators can fit in there then).
This because multiplying (or thus basically linear scaling) does not
change the ordering. That will remain the same.
For example, you know by experience that if given that John is bigger
than Vanessa which is in turn bigger than Susanne, then making each one
if possibly ten times bigger at once, then after that John is still
bigger than Vanessa which is still bigger than Susanne.
So here after multiplying, the '^' becomes then 50, and '*' becomes 40,
and '+' becomes 30. So still the '^' has a bigger priority than the '*'
and this a higher than '+'. And that is what is wanted.
So to add new operators to your table, you ask yourself:
is the priority of that operator HIGHER, EQUAL or LOWER than
another operator (or similarly operand), and
then accordingly
assign it a HIGHER,EQUAL or LOWER number
and put it in the right priority position in your table.
The only exception are thus the brackets.
They have a variable priority.
When on the INPUT stack:
the '(' bracket has the HIGHEST priority (or thus the highest number,
9).
And the ')' has the LOWEST priority (or thus the lowest number, 2).
But after that it roles interchange.
When on the STACK stack
the '(' gets the LOWEST priority (or thus the lowest number, 2)
And the ')' gets the HIGHEST priority (or thus the highest number, 9)
The same story goes for other brackets like {}, [], ...
Remark: The special 'I am finished' operator '#' has thus to have an
even lower priority or number (here the number 0) in your table.
---
---
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
(according to the input priority table)
than the last token on the stack
(according to the stack priority table)
push its value on this stack
else
3. if this token has a SMALLER OR EQUAL PRIORITY
(according to the input priority table)
than the last token on the stack
(according to the stack priority table)
1. remove all stack tokens
with a priority higher or equal
than that token, and put
this removed tokens (except
open or closed brackets) 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 |
+---+---+---+---+---+---+---+---+---+---+---+
---
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
+---+---+---+---+---+---+---+---+---+---+---+
| | 3 | + | 4 | ) | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| # | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
That is a '(', or thus an open bracket.
---
Look in your INPUT PRIORITY table for the priority of
the token '('.
That is 9 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token '#'.
That is 0 for this token..
As the token '(' has a GREATER priority than
the token '#', push the token '(' on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | 3 | + | 4 | ) | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| ( | # | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | + | 4 | ) | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| ( | # | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
That is a '3'
---
Look in your INPUT PRIORITY table for the priority of
the token '3'.
That is 9 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token '('.
That is 2 for this token.
As the token '3' has a GREATER priority than
the token '(', push the token '3' on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | + | 4 | ) | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | ( | # | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | 4 | ) | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | ( | # | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
That is a '+'
---
Look in your INPUT PRIORITY table for the priority of
the token '+'.
That is 3 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token '3'.
That is 9 for this token.
As the token '+' has a SMALLER priority than
the token '3', pull the token '3' from the stack,
and add it to the end of your result.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | 4 | ) | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| ( | # | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Look in your INPUT PRIORITY table for the priority of
the token '+'.
That is 3 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token '('.
That is 2 for this token..
As the token '+' has a GREATER priority than
the token '(', push the token '+' on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | 4 | ) | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| + | ( | # | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | ) | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| + | ( | # | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
That is a '4'
---
Look in your INPUT PRIORITY table for the priority of
the token '4'.
That is 9 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token '+'.
That is 3 for this token.
As the token '4' has a GREATER priority than
the token '+', push the token '4' on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | ) | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| 4 | + | ( | # | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| 4 | + | ( | # | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
That is a ')'
---
Look in your INPUT PRIORITY table for the priority of
the token ')'.
That is 2 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token '4'.
That is 9 for this token.
As the token ')' has a SMALLER priority than
the token '4', pull the token '4' from the stack,
and add it to the end of your result.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| + | ( | # | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Look in your INPUT PRIORITY table for the priority of
the token ')'.
That is 2 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token '+'.
That is 3 for this token.
As the token ')' has a SMALLER priority than
the token '+', pull the token '+' from the stack,
and add it to the end of your result.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| ( | # | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Look in your INPUT PRIORITY table for the priority of
the token ')'.
That is 2 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token '('.
That is 2 for this token.
As the token ')' has an EQUAL priority as
the token '(', pull the token '(' from the stack,
and because it is a bracket, just simply
discard it (that is you will not use it anymore).
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| # | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Look in your INPUT PRIORITY table for the priority of
the token ')'.
That is 9 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token '#'.
That is 0 for this token.
As the token ')' has a GREATER priority than
the token '#', push the token ')' on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | * | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| ) | # | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| ) | # | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
That is a '*'
---
Look in your INPUT PRIORITY table for the priority of
the token '*'.
That is 4 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token ')'.
That is 2 for this token.
As the token '*' has a GREATER priority than
the token ')', push the token '*' on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | 5 | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| * | ) | # | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| * | ) | # | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
That is a '5'
---
Look in your INPUT PRIORITY table for the priority of
the token '5'.
That is 9 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token '*'.
That is 4 for this token.
As the token '5' has a GREATER priority than
the token '*', push the token '5' on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | + | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| 5 | * | ) | # | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| 5 | * | ) | # | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
That is a '+'
---
Look in your INPUT PRIORITY table for the priority of
the token '+'.
That is 3 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token '5'.
That is 9 for this token.
As the token '+' has a SMALLER priority than
the token '5', pull the token '5' from the stack,
and add it to the end of your result.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| * | ) | # | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | 5 | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Look in your INPUT PRIORITY table for the priority of
the token '+'.
That is 3 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token '*'.
That is 4 for this token.
As the token '+' has a SMALLER priority than
the token '*', pull the token '*' from the stack,
and add it to the end of your result.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| ) | # | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | 5 | * | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Look in your INPUT PRIORITY table for the priority of
the token '+'.
That is 3 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token ')'.
That is 9 for this token.
As the token '+' has a SMALLER priority than
the token ')', pull the token ')' from the stack,
and because it is a bracket, just simply
discard it (that is you will not use it anymore).
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| # | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | 5 | * | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Look in your INPUT PRIORITY table for the priority of
the token '+'.
That is 3 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token '#'.
That is 0 for this token.
As the token '+' has a GREATER priority than
the token '#', push the token '+' on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | 6 | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| + | # | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | 5 | * | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| + | # | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | 5 | * | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
That is a '6'
---
Look in your INPUT PRIORITY table for the priority of
the token '6'.
That is 9 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token '+'.
That is 3 for this token.
As the token '6' has a GREATER priority than
the token '+', push the token '6' on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | - | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| 6 | + | # | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | 5 | * | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| 6 | + | # | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | 5 | * | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
That is a '-'
---
Look in your INPUT PRIORITY table for the priority of
the token '-'.
That is 3 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token '6'.
That is 9 for this token.
As the token '-' has a SMALLER priority than
the token '6', pull the token '6' from the stack,
and add it to the end of your result.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| + | # | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | 5 | * | 6 | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Look in your INPUT PRIORITY table for the priority of
the token '-'.
That is 3 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token '+'.
That is 3 for this token.
As the token '-' has an EQUAL priority as
the token '+', pull the token '+' from the stack,
and add it to the end of your result.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| # | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | 5 | * | 6 | + | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Look in your INPUT PRIORITY table for the priority of
the token '-'.
That is 9 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token '#'.
That is 0 for this token.
As the token '-' has a GREATER priority than
the token '#', push the token '-' on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | 7 |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| - | # | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | 5 | * | 6 | + | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Take off the next token.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| - | # | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | 5 | * | 6 | + | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
That is a '7'
---
Look in your INPUT PRIORITY table for the priority of
the token '7'.
That is 9 for this token.
Look in your STACK PRIORITY table for the priority of the
current last token on the stack, that is the token '-'.
That is 3 for this token.
As the token '7' has a GREATER priority than
the token '-', push the token '7' on the stack.
---
expression
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your 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
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your stack
+---+---+---+---+---+---+---+---+---+---+---+
| # | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
your result
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | + | 5 | * | 6 | + | 7 | - | | |
+---+---+---+---+---+---+---+---+---+---+---+
---
Your result contains now your original infix expression converted to
postfix or reverse polish notation.
---
---
Book: see also:
---
[book: Dvorak, Stanislav / Musset, Anthony - BASIC in action - p. 221 -
'translation of an arithmetic expression' -
http://www.amazon.com/exec/obidos/tg/detail/-
/0408013958/qid=1067346267/sr=1-6/ref=sr_1_6/103-2842924-9105401?
v=glance&s=books]
---
[book: Tremblay, Jean-Paul / Bunt, Richard B. - p. 464 - 'conversion
of infix expression to Polish notation' - an introduction to computer
science - http://www.amazon.com/exec/obidos/tg/detail/-
/0070651671/qid=1067346345/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
----------------------------------------------------------------------
