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

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

Due and late dates and times

Due: March 25 23:59
Late: April 1, 23:59

Overview

The object of this assignment is to parse infix expressions, convert them to expresion trees, and evaluate these expression trees. Use ( OR FIX ) your iterator TokenIter from P2. Also use the starter code made available in week 5, and the Expression Parse code you worked in in recitation 6. In debug mode, make sure you follow the indentation convention started in the provided code. The java codes making up this assignment are:

TokenIter.java, use, or fix, your TokenIter code from P2
TreeNode.java, don't change this code.
Tree.java, use and complete the code provided in week 5.
ParseExpr.java, use, or fix, the code you worked in recitation 6.
ParseTreeExpr.java, use and complete the code provided in week 5.
ParseException.java, don't change this code.
ParseDriver.java, don't change this code.
ParseTreeDriver.java, don't change this code.
in, an example input file, play with more inputs in this or other input files.

The syntax for infix expressions is defined as follows:

  expr = term ( ("+" | "-") term )*

  term = factor ( ("*" | "/") factor )*

  factor = number | "(" expr ")"

As discussed in class, this iterative, not left recursive, grammar can be directly transformed into a predictive parser, where every non-terminal becomes a method parsing that non-terminal.

You need to work on the following codes.

Tree

Your Tree code needs a postorderEval method (see ParseTreeDriver):

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

which evaluates the (expression) Tree. It evaluates the operands, and then evaluates the operator. All nodes return an Integer value.

TokenIter

Use, or fix, your TokenIter code from P2.

ParseExpr

Use, or fix, the code you worked in recitation 6.

ParseTreeExpr

Extend the code provided in week 5. Be aware that that code only delt with sums.

Debug mode

Follow the debug reporting provided in ParseExpr and ParseTreeExpr. Your methods expr, term, factor and number should provide debug info (indent + "expr" for example)

Testing and submitting your code

pResDB contains the ParseDriver output for input file in, when in debug mode.
pRes contains the ParseDriver output for input file in, when not in debug mode.
ptResDB contains the ParseTreeDriver output for input file in, when in debug mode.
pRes contains the ParseTreeDriver output for input file in, when not in debug mode.

Use the Checkin webserver to exercise and submit your code. Submit your a P3.jar file containing TokenIter.java, Tree.java, ParseExpr.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 2015 P3: Parsing infix expressions, building and evaluating expression trees