CMPS 144L
Lab Activity: FPAE Evaluation
Name____________________
  

public Integer evaluate( Expr e ) {

  Stack operandStk = new StackX();
  Stack operatorStk = new StackX();
  Token t;

  while (e.hasMoreTokens()) {
    t = e.nextToken();
    if (t is a left parenthesis) { }
    else if (t is an integer literal)  
      { operandStk.push(t); }
    else if (t is an operator)
      { operatorStk.push(t); }
    else if (t is a right parenthesis) {
      Integer y = operandStk.pop();
      Integer x = operandStk.pop();
      Operator op = operatorStk.pop();
      operandStk.push( op.apply(x,y) ); 
    }
  }
  return operandStk.topOf();
}
Apply the algorithm shown to the right to the fully-parenthesized arithmetic expression 

((3 + 7) * (((8 - 2) * 4) / (1 + 2)))

Show the history of the two stacks in the space provided beow. Specifically, for each occurrence of a right parenthesis, show the contents of the stacks immediately before and immediately after it has been processed.

Repeat this activity for the FPAE on the backside of this page. 













  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  +----+ +----+    +----+ +----+       +----+ +----+    +----+ +----+
   before 1st        after 1st          before 2nd        after 2nd


  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  +----+ +----+    +----+ +----+       +----+ +----+    +----+ +----+
   before 3rd        after 3rd          before 4th        after 4th 



  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  +----+ +----+    +----+ +----+       +----+ +----+    +----+ +----+
   before 5th        after 5th          before 6th        after 6th

Repeat what you did on the first page with respect to the following FPAE: 

((3 + (12 / 6)) * ((8 - 7) * (4 + 2)))


  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  +----+ +----+    +----+ +----+       +----+ +----+    +----+ +----+
   before 1st        after 1st          before 2nd        after 2nd


  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  +----+ +----+    +----+ +----+       +----+ +----+    +----+ +----+
   before 3rd        after 3rd          before 4th        after 4th 



  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  |    | |    |    |    | |    |       |    | |    |    |    | |    |
  +----+ +----+    +----+ +----+       +----+ +----+    +----+ +----+
   before 5th        after 5th          before 6th        after 6th