P3: CS 200 Data Structures and Algorithms (Fall 2015)

CS 200, Fall 2015
P3: Parsing infix Boolean expressions, building and evaluating expression trees

Due and late dates and times

Due: October 27, 23:59
Late: October 29, 23:59

Overview

The object of this assignment is to parse infix Boolean expressions, convert them to expression trees, and evaluate these expression trees. Use ( OR FIX ) your TokenIter from P2. Use the InfixSum code that parses arithmetic infix expressions, made available in week 6, as an example. Debug mode will no longer be enforced, or tested.

The syntax for infix expressions is defined as follows:

  expr = term ( "or" term )*

  term = factor ( "and" factor )*

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

As discussed in class, this iterative (not left recursive) grammar can be transformed directly into a predictive parser, where every non-terminal becomes a method parsing that non-terminal, and produces the TreeNode associated with the expression tree.

You need to work on the following codes.

TokenIter.java,
use, or fix, your TokenIter code from P2
TreeNode.java, don't change this code, but you can run it.
Tree.java,
implement the postorderEval(TreeNode node) method. You can run it and check the validity of your code.
ParseTreeExpr.java,
parse boolean expressions and create their expression trees. Use the InfixSum code provided in week 6 as an example.
ParseException.java, don't change this code.
ParseTreeDriver.java, this is the main client code, taking input files and exercising your codes. don't change this code. You need a proper TokenIter.java to make this code compile.
in,
an example input file, play with more inputs in other input files.

Tree

Your Tree code needs a proper implementation of the postorderEval(TreeNode node) method , that is called by:

    // if tree empty return null
    // else evaluate the tree by postorder traversal 
    // and return its value
    public Boolean  postorderEval(){
    	Boolean res = null;
    	if(!isEmpty()){
    		res = postorderEval(root);
    	}
    	return res;
    }

which evaluates the (boolean expression) Tree. It evaluates the operands, and then evaluates the operator. All nodes return a Boolean value.

TokenIter

Use, or fix, your TokenIter code from P2.

ParseTreeExpr

Extend the code provided in week 6. Be aware that that code only dealt with sums. Here you need to deal with "not", "and" and "or" internal nodes, and "true" and "false" leaves.

Testing and submitting your code

res contains the ParseTreeDriver output for input file in.

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

Make sure you put ***java** files in your jar (not class files). The TAs can help you creating a proper jar file.