Evaluating a Postfix expression
(C) Samuel Marateck 2004

The following explains how to write a program that uses a stack to
evaluate a postfix expression, e.g., 3 4 * 5 +, directly. The algorithm is:

(1) As you read the expression from left to right, push each operand on the
stack (here 3 and 4) until you encounter an operator (here, *).

(2) Pop the stack twice and perform a calculation using the operator and
the two operands popped (here, 3*4 or 12). Push this result (here, 12)
on the stack.

(3) Next push 5 on the stack and when the "+" is encountered, pop 5
and then 12 from the stack and get 5 + 12 or 17. Then push 17 onto the
stack. Since there is no more data, pop the stack and obtain 17 as the
final answer. If during the program you can't pop the stack or there
is data remaining on the stack at the end, then our postfix expression
is wrong. 

Converting an Infix to a Postfix expression without parentheses

The algorithm is:

(1) As you read the input string from left to right, add each operand to the
    output string (in 3 * 4 + 5, add 3 to the output string).
(2) When you encounter the first operator (here, *) push it on the stack.
(3) Add the next operand to the output string (it is now 3 4).
(4) When you encounter the next operator (here, +), while the operator on
    the stack top (here, *) has a higher or equal precedence to this
    operator, pop it and add it to the output string (it is now 3 4
    *). Push the operator (here, +) on the stack.
(5) Continue this process until you read the entire input string (in our
    example, the output string becomes 3 4 * 5).
(6) Pop the stack and add the operators to the output string until the stack
    is empty (our output becomes 3 4 * 5 +).

The psuedocode that is in the while loop block performed when a boolean
variable valid is true and the string index less than or equal to the string's
the length is:

if( operand( token ) )
    postfix = postfix + token
else if( operator( token ) )
     while( ! stack.isEmpty() && precedence( stack.peek(), token )  )
          postfix = postfix + stack.pop();
     stack.push( token )
else valid = false

After the loop is done and valid is true then
   while( ! stack.isEmpty() )
        postfix = postfix + stack.pop();

The precedence is such that:
  Top of stack          Precedence over
----------------------------------------
  '*', '/'              everything
  '+', '-'               '+', '-'

Converting an Infix to a Postfix expression with parentheses.

When a '(' is encountered, its always pushed on the stack. When its on
the stack, all incoming tokens (except the ")" ) have precedence over
it and are pushed on the stack.  When a ')' is encountered, everything
on the stack to the first '(' is popped and added to the postfix
expression. Then the '(' is popped and discarded.

Lets look at (2+3)/(4*5)

(1) The '(' is pushed.
(2) The 2 is added to the output.
(3) The '+' is pushed on the stack.
(4) The 3 is added to the out; its now 23.
(5) The ')' triggers the '+' to be popped and added to output; its now 23+.
(6) The '(' is popped and discarded.
(7) The '/' is pushed.
(8) The '(' is pushed.
(9) The 4 is added to the output; its now 23+4
(10) The "*' is pushed.
(11) The 5 is added to the output; its now 23+45
(12) The  ')' triggers the '*' to be popped and added to output; its now 23+45*
(13) The '(' is popped and discarded.
(14) The eoln is now true, so if no invalid characters have been encountered.
     all the tokens remaining on the stack are popped  and added to the output;
     its now  23+45*/

The psuedocode that is in the while loop block performed when a boolean
variable valid is true and the string index less than or equal to the string's
the length is:


if( operand( token ) )
    postfix = postfix + token
else if (operator( token ) )
     while(  !stack.isEmpty() && precedence( stack.top(), token ) )
          postfix = postfix + stack.pop();
     if( token  != ')' )
          stack.push( token )
      else
          pop stack and discard it
else valid = false

The precedence is such that:
  Top of stack          Precedence over
----------------------------------------
  '('                   Nothing, everything else pushed on stack
  '*', '/'              everything except '('
  '+', '-'               '+', '-', ')'