CMPS 144L
Lab Activity: FPAE Evaluation
Name____________________
  

public Integer evaluate( Expr e ) {

  Stack operandStk = new StackX();
  Stack operatorStk = new StackX();
  e.startTokenizer();

  while (e.hasMoreTokens()) {
    Token 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. Note that if two right parentheses occur consecutively, the contents of the stacks immediately after the first one is processed will be identical to the contents of the stacks immediately before the second one is 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