In the process of creating machine code from source code, compilers translate
infix expressions to postfix expressions. Example:
2*3+4 --> 23*4+
The rule is that each operator follows its two operands.
The algorithm to make this transition uses a stack.
In the process of evaluating a postfix expression, another stack is used.
Translating Infix to Postfix
You can remember the method "heuristically" and also describe it by an
algorithm:
Heuristic method
Fully parenthesize the expression - to represent your desired
priorities or the default precedence of the operators
move each operator to its nearest right parenthesis
remove parentheses
Example:
2*3+4 --> ((2*3)+4) --> 23*4+
Algorithm
Takes input expression infix and produces output expression
postfix.
Uses the 2 notions of precedence:
in-stack precedence isp()
incoming precedence icp().
For C++ operators, isp() = icp() = C++ precedence. For left parentheses
(, we use isp('(') = 8, and icp('(') = 0. We also use
a termination symbol appended to end of infix, with isp('#') =
8.
Uses a stack for operators, but passes operands thru to output
Steps in the algorithm:
push # onto stack
Loop thru infix from left to right, getting tokens x
one at a time
if x is an operand, output to postfix
else if x is a right parenthesis, pop stack until left parenthesis
else
do: pop y from stack while isp(y) <= icp(x)
push last y back onto stack
push x onto stack
Thought question: the preceding algorithm uses the default precedences of
operators to substitute for fully parenthesizing the expression. If the
expression were fully parenthesized first, could the algorithm be simplified?
Evaluating postfix expressions
Scan the expression left to right, this time stacking operands, then
pop operators as needed when the operand that applies to them is reached.
Algorithm
Loop thru postfix left to right, getting tokens x
if x is an operand, push onto stack
if x is an operator,
pop its previous operand(s)
evaluate the expression
push the result
Example: the expression is shown above, and at each location in the expression,
the operand stack is shown below