P3: CS 200 Data Structures and Algorithms (Spring 2017)

CS 200, Spring 2017
P3: Parsing infix Boolean expressions, building and evaluating expression trees

Due and late dates and times

Due: March 23
Late: March 27

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, as an example. Debug will not be 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 with the following codes.

Debug.java, used for debugging.
TokenIter.java,
The provided code is an empty shell to allow compilation. Use, or fix, your TokenIter from P2.
TreeNode.java. Complete this code.
Tree.java. Complete this code. When done, run it and check the validity of your TreeNode and Tree code.
ParseTreeExpr.java. Complete this code. Parse boolean expressions and create their expression trees. Use the InfixSum code provided in recitation 6 as an example.
ParseException.java, provided, don't change this code.
Driver.java, this is the main client code, taking input files and exercising your codes, don't change this code.
in, an example input file, play with more inputs in other input files.

The generated tree should treat "and" and "or" as left associative, i.e. true and true and false should have the following Driver output:

next line: [true and true and false]
expression tree:
and
 and
  true
  true
 false
result: false

Tree

Your Tree code needs a proper implementation of the postorderEval(TreeNode node) method , which evaluates the (boolean expression) Tree. It evaluates the operands, and then evaluates the operator. All nodes return a Boolean value.

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, TreeNode.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.

CS 200, Spring 2017 P3: Parsing infix Boolean expressions, building and evaluating expression trees

Due and late dates and times

Overview

Tree

Testing and submitting your code

CS 200, Spring 2017
P3: Parsing infix Boolean expressions, building and evaluating expression trees