CS 112 Lab 5

We will implement a calculator for the "infix" expression, i.e. an expression that might look like

( ( 3 + 5 ) x ( 4 - 6 ) ) / ( 7 + 2 x 3 - 9 )

We do not implement operator precedence but allow parenthesis; hence any valid math expression can be computed.

The evaluation of an infix expession consists of two steps:

• Build an expression-tree to decompose the given expression into a sequence of binary operations. An expression-tree is a binary tree with each node storing an operator and pointers to the left and right sub expressions.
  
  A demo for construction of an expression tree correponding to the above example is shown here,
  
  http://cs-people.bu.edu/tvashwin/cs112_spring08/lab05_files/expressionTree.ppt
  
  
• Evaluate the expression by traversing the expression-tree
  
  This is a simple recursive evaluation of the left and right child nodes of the expression-tree.

Download class files for the lab below,

• ExpressionTree.java
  
  This class does all the work in parsing a math expression to yield an expression-tree and then evaluate it.
  
  Task: fill in the ???? parts to finish the class.
  
  
• ExpressionTester.java
  
  This is the client class to test our ExpressionTree. It has a method to generate a lengthy recursive fraction.
  

Posted here after labs.

ExpressionTree.java

http://cs-people.bu.edu/tvashwin/cs112_spring08/lab05.html