Due and late dates and times

• Due: Apr 20
• Late: Apr 24

Overview

  equation = identifier "=" expr
 
  expr     = term ( "or" term )*

  term     = factor ( "and" factor )*

  factor   = "not" factor | "(" expr ")" | "true" | "false" | identifier

An identifier is a letter followed by zero or more letters or digits, but not "true" or "false" or "not" or "and" or "or".

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

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

a1 = true
b2 = a1 and not false
c3 = a1 or b2

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 an IdVal, 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 IdVal in a symbol table. The symbol table is implemented using a Binary Search Tree, similar to the BST code provided in Lecture L7 and Recitation R7. An IdVal has a String key (an identifier), and a Boolean value (the result of evaluating its right hand side).

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, Boolean value) pairs.

The identifiers in an expression must be 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.

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

next line: a1 = true
result: [a1: true]
next line: b2 = a1 and not false
result: [b2: true]
next line: c3 = a1 or b2
result: [c3: true]

Work with the following codes:

• TokenIter.java, use or fix your iterator 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 Boolean postorderEval(TreeNode node, BST symTab) throws BSTException
  

  When encountering an identifier in an expression Tree, postorderEval looks up the value associated with the identifier in the BST symTab, and uses it to evaluate the expression.
• Driver.java is provided, don't change this code. 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:

     public IdVal line(BST symboTable) throws BSTException, ParseException
  

  must now read a line consisting of an identifier, a "=" sign, and an expression, and now must return an IdVal: an (identifier,value) pair, containing the left hand side identifier and the result of evaluating the right hand side expression, and store the IdVal in the symbol table.

• ParseException.java, BSTException.java. Equation methods throw ParseExceptions and BSTExceptions. Use the Exception classes provided earlier. Notice that Driver now catches ParseExceptions and BSTExceptions.
• BSTNode.java, IdVal.java, and Key.java are provided. Don't change these codes.
• BST.java must implement a Binary Search Tree. The provided shell does not compile because it has methods missing. Use the BST code from recitation R7 as a guide.

Testing and submitting your code

• res contains the "java Driver in" output for input file in.

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

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