Due and late dates and times

• Due: Nov 10 23:59
• Late: Nov 14 23:59

Overview

  equation ::=   identifier "=" expr
 
  expr     ::=   term ( ("+" | "-") term )*

  term     ::=   factor ( ("*" | "/") factor )*

  factor   ::=   "-" factor | identifier | number | "(" expr ")"

An identifier is a letter followed by zero or more letters or digits:

 identifier = [A-Za-z]([A-Za-z0-9])*

Here is an example of 3 equations, each one on a line:

a = 3-4 - -5
b = a*7 + 11
c = a+-b

The goal of this project is to read lines, that are either empty or contain one equation, evaluate the expression on the right hand side, store the key and value in a Symbol, where the key is the identifier on the left hand side, and the value is the result of evaluating the right hand side, and store the symbol in a symbol table. The symbol table is implemented using a Binary Search Tree.

Notice that we now have two very different trees: an expression tree to represent and evaluate expressions, and a Binary Search Tree to implement a symbol table that stores (String identifier, Integer value) pairs.

The identifiers in an expression are defined in previous equations. Identifiers are not redefined, i.e. there is only one definition of each identifier. When during the postorder evaluation of an expression tree an identifier is encountered, its value must be looked up in the symbol table, and used in the evaluation of the expression.

For example, when parsing and evaluating a file with the three equations above, the following output is generated by EquationDriver (see below):

next line: a = 3-4 - -5
result: [a: 4]
next line: b=a*7+11
result: [b: 39]
next line: c = a+-b 
result: [c: -35]

Work with the following codes:

• TokenIter.java, use or fix your TokenIter from P3, and add "=" signs and identifiers to the tokens that can occur on a line.
• TreeNode.java, use TreeNode.java from P3.
• Tree.java, use and add to Tree.java from P3. The postorderEval method now takes an extra parameter, the symbol table: BST symTab.
  

     public Integer postorderEval(TreeNode node, String indent, BST symTab) throws BSTException
  

  When encountering an identifier in an expression Tree, postorderEval looks up the value associated with the identifier in the symbol table, and uses it to evaluate the expression.
• EquationDriver.java is provided, don't change this code. The equation driver initializes the symbol table, and repeatedly reads lines from a file, creates a TokenIterator and a next Equation, and calls the line method of the Equation class.
• Equation.java replaces ParseTreeExpr from P3. Where in P3 a line contains an expression, in P4 a line contains an equation:

  identifier "=" expression
  

  The line method in equation must now return a symbol: an (identifier,value) pair, containing the left hand side identifier and the result of evaluating the right hand side expression, and store the symbol in the symbol table.
• ParseException.java, BSTException.java, Equation methods throw ParseExceptions and BSTExceptions. Use the Exception classes provided earlier. Notice that EquationDriver now catches ParseExceptions and BSTExceptions, see the EquationDriver.java code.
• Symbol.java, Key.java and BSTNode.java are provided. don't change these. BST.java, BSTNode.java, Symbol.java, and Key.java are used for the symbol table, implemented by a Binary Search Tree. Start from the code you worked on in recitation (Symbol was called IdVal in the recitation) R7, and implement the insertItem and retrieveItem methods in BST.java.

Testing and submitting your code

• outOK contains the EquationDriver output for input file inOK.

Use the Checkin webserver to exercise and submit your code. Submit a P4.jar file containing TokenIter.java, BST.java, Tree.java , Equation.java **ONLY**.

Make sure you put ***java** files in your jar (not class files).