CS 200, Spring 2017
P4: Parsing and evaluating equations

Due and late dates and times

Overview

The object of this assignment is to parse and evaluate equations. Equations are of the form:
  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:

Testing and submitting your code

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).