Infix to postfix

Evaluating expressions

Use of stacks in evaluating expressions:

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.

You can remember the method "heuristically" and also describe it by an algorithm:

Heuristic method
1. Fully parenthesize the expression - to represent your desired priorities or the default precedence of the operators
2. move each operator to its nearest right parenthesis
3. 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:
  1. in-stack precedence isp()
  2. 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:
1. push # onto stack
2. Loop thru infix from left to right, getting tokens x one at a time
  1. if x is an operand, output to postfix
  2. else if x is a right parenthesis, pop stack until left parenthesis
  3. else
    1. do: pop y from stack while isp(y) <= icp(x)
    2. push last y back onto stack
    3. 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?

Scan the expression left to right, this time stacking operands, then pop operators as needed when the operand that applies to them is reached.