CS 200: P4: Parsing and evaluating equations

Overview

The object of this assignment is to parse and evaluate boolean equations. Equations are of the form:

    equation = identifier "=" expr
    expr     = term ( "|" term )*
    term     = factor ( "&" factor )*
    factor   = "!" factor | "(" expr ")" | "0" | "1" | identifier

| means boolean or
& means boolean and
! means boolean not
0 means false
1 means true

An identifier is:

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

Here are several equations, one per line:

    a1 = 1
    b2 = a1 & ! 0
    c3 = a1 | b2
    detroit=!!!c3

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 excercised in Recitation R7. The difference is that for this assignment an IdVal has a String key (an identifier), and a Boolean (not 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 EquationDriver, see below):

next line: a1 = 1
result: [a1: true]
next line: b2 = a1 & ! 0
result: [b2: true]
next line: c3 = a1 | b2
result: [c3: true]
next line: detroit=!!!c3
result: [detroit: false]

Work with the following code:

TokenIter.java
- Update TokenIter from P3.
TreeNode.java
- Use TreeNode.java from P3.
Tree.java
- Update 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.
EquationDriver.java
- 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.
- Whereas 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 EquationDriver now catches ParseExceptions and BSTExceptions, see the EquationDriver.java code.
BST.java, BSTNode.java, IdVal.java, and KeyItem.java
- are used for the symbol table, implemented by a Binary Search Tree. Use the code from R7, but change your IdVals to (String,Boolean) pairs.

Details

Throw only the exceptions listed:
- ParseException for a parsing error
- BSTException if:
  - a duplicate symbol tries to go into the symbol table
  - an undefined symbol is read from the symbol table
Spaces are allowed anywhere except inside an identifier.
We will only test your code with valid tokens.
We will test your code with invalid expressions.

Testing and submitting your code

eqDrRes contains the equationDriver output for input file in.

Use the Checkin webserver to exercise and submit your code. Submit a P4.jar file containing:

Equation.java
IdVal.java
TokenIter.java
Tree.java

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