CPSC 2120 - DAY 3
MAY 13, 2016

===============================================================================

infix expression: z = a * (x+y) + z * c ^ (2 - (-d +w)) / x;

x = z * a + b - - c ^ d + (a + b - c ^ d);
    |___|         |___|    |___|    |____|

Converting expressions from infix to postfix


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      


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: z a x y + * z c 2 ~ w + - ^ * x / + =     


|  | ~  <- unary minus represented by tilde
|  |
|  |
|  |
|  |
|  |
|  |
|  |
|@ | <- Bottom Marker
|__|



FORTRAN - John Backus / IBM
COBOL - Grace Hopper


*** Review Infix to Postfix, practice postfix to quadruples.