Converting expressions from infix to postfix

• 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.
• 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 Java/C++ operators, isp() = icp() = Java/C++ precedence.

  • Uses a stack for operators, but passes operands through to output
  Steps in the algorithm:
  1. push @ onto stack
  2. Loop through 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

Symbol   In-Stack Priority  In-Coming Priority
======   =================  ==================

@              -2                  -      // stack bottom marker
=              -1                 -1
^               3                  4
-               3                  4      // unary minus
*, /            2                  2
+, -            1                  1
(               0                  5      // <= note new ICP=5



Pseudo-code Algorithm:

void InfixToPostfix (StringTokenizer E) {

   // assume that E is the infix arithmetic expression and that
   // stack will hold operators and is initially empty
 
   stack.push("@");               // initialize stack with bottom marker

   while (true) {
      String token = E.nextToken();

      if ( token == ";" ) {            // end of expression
         while (stack.top() != "@")  // flush stack
            System.out.println(stack.pop() + " ");
         stack.pop();                // empty stack
         return;
      } // token == ";"

      else if (token is an operand)   // the sequence of operands is indentical 
         System.out.println(token);   // in both infix and postfix

      else if (token == ")") {        // look for matching "("
         while (stack.top() != "(")   
            System.out.println(stack.pop() + " ");
         stack.pop();
      } // token == ")"

      else {                     // token is an operator

         while(ISP(stack.top()) >= ICP(token))
            System.out.println(stack.pop() + " ");
         stack.push(token);

      } // token is an operator

   } // while
      
      
} // InfixToPostfix

Postfix expression evaluation

/**
 * This class can take a variable number of parameters on the command
 * line. Program execution begins with the main() method. The class
 * constructor is not invoked unless an object of type 'Class1'
 * created in the main() method.
 */
public class PostFix
{
	/**
	 * The main entry point for the application. 
	 *
	 * @param args Array of parameters passed to the application
	 * via the command line.
	 */
	public static void main (String[] args)
	{
		Stack s = new LinkedStack();
		
		try {
			for (int i = 0; i < args.length; i++) {
				if (args[i].equals("+")) {
					int a = ((Integer) s.pop()).intValue();
					int b = ((Integer) s.pop()).intValue();
					s.push(new Integer(a + b));
				}
				else if (args[i].equals("-")) {
					int a = ((Integer) s.pop()).intValue();
					int b = ((Integer) s.pop()).intValue();
					s.push(new Integer(b - a));
				}
				else if (args[i].equals("*")) {
					int a = ((Integer) s.pop()).intValue();
					int b = ((Integer) s.pop()).intValue();
					s.push(new Integer(b * a));
				}
				else if (args[i].equals("/")) {
					int a = ((Integer) s.pop()).intValue();
					int b = ((Integer) s.pop()).intValue();
					s.push(new Integer(b / a));
				}
				else {
					s.push(new Integer(args[i]));
				}
			}
		
			System.out.println(((Integer) s.pop()).toString());
		}
		catch (StackException se) {
			se.printStackTrace();
		}
	}
}

Recursion Removal:

• Quicksort

  QUICKSORT WITH DETERMINISTIC PIVOT CHOICE (RECURSIVE VERSION
  AND NONRECURSIVE VERSIONS):
  
  Here we will take pivot to be the first element in the part of
  the list we are sorting.  The procedure "split"  calculates
  pivot and returns pivot and the list, divided into values <
  A[pivot] and values >= A[pivot]
  
  procedure split(first, last, pivot)
       x = A[first]
       pivot = first
       for index = first + 1 to last do
             if A[index] < x then
                   pivot = pivot + 1
                   swap( A[pivot], A[index])
       swap( A[first], A[pivot])
       return pivot
  
  recursive version:                  |nonrecursive version:
  quicksort(first,last)               |    Push A[0] , ... , A[n-1] onto stack
      if first < last then            |    first = 0; last = n-1;
        split(first, last, pivot)     |    while stack is not empty do
        quicksort (first, pivot - 1)  |        Pop A[first] , ... , A[last]
        quicksort( pivot+1, last)     |        while first < last do
                                      |           split (first, last, pivot)
                                      |           push A[pivot+1], ... , A[last]
                                      |           last = pivot - 1