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

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

Due and late dates and times

Due: Thursday Oct 27
Late: Monday Oct 31

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 on, in recitation 6. The java codes making up this assignment are:

TokenIter.java, use, or fix, your TokenIter code from P2.
TreeNode.java, Provided, don't change this code.
Tree.java, use and extend the code provided in week 5 in InfixSum.jar.
ParseTreeExpr.java, use and extend the code provided in InfixSum.jar.
ParseException.java, don't change this code.
Driver.java, don't change this code.
in, an example input file, play with more inputs in this or other input files.
inMin, another example input file.

The syntax for infix expressions is defined as follows:

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

  term = factor ( ("*" | "/") 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 Driver):

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

ParseTreeExpr

Extend the code provided in week 5 in InfixSum.jar. Be aware that InfixSum only delt with sums, so you need to change your expr method, and create term and factor methods.

Debug mode

You can follow the debug reporting style provided in ParseExpr and ParseTreeExpr. Your methods expr, term, factor and number can, but don't have to, provide debug info (indent + "expr" for example). Your code will not be tested in debug mode.

Testing and submitting your code

ResIn contains the Dchriver output for input file in.
ResInMin contains the Driver output for input file inMin.

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

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

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