CS 200 P3: Parsing infix double expressions, building and evaluating expression trees
Overview
The object of this assignment is to parse infix double expressions, convert
them to expression trees, and evaluate these expression trees. Modify
(and perhaps first finish)
your TokenIter from P2.
Debug mode will no longer be enforced, or tested.
The syntax for infix expressions is:
expr = term ( ("+" | "-") term )*
term = factor ( ("/\" | "\/") factor )*
factor = "abs" factor | "(" expr ")" | flopon
flopon = digits ("." digits)? ("e" ("+"|"-") digits)?
digits = [0-9]+
- Do not assume that the syntax of a flopon is simply that of
a Java floating-point number.
- The “abs” unary operator yields the
absolute value
of its argument. It is not a function.
- The “/\” binary operator yields the maximum of its operands.
- The “\/” binary operator yields the minimum of its operands.
- All binary operators are left-associative, e.g., 1-2-3
means (1-2)-3, not 1-(2-3).
- 1.2 /\ 4 yields 4
- 1.2 \/ 4 yields 1.2
- 100 /\ 3.4e+45 yields 3.4e+45
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 code:
- TokenIter.java:
- Use, or fix, your TokenIter code from P2, updated for these tokens.
- Spaces are optional anywhere except inside of an operator or a number
(no “a bs”, “/ \”, or “3.1 4159”).
- Spaces are only required between alphanumeric tokens
(“abs” and numbers).
- As before, bad tokens are silently ignored.
- 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 double expressions and create their expression trees.
- ParseException.java
- 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.
- res
- Expected output from the input file in.
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 Double postorderEval(){
Double res = null;
if (!isEmpty())
res = postorderEval(root);
return res;
}
which evaluates the (double expression) Tree. It evaluates the operands, and
then evaluates the operator. All nodes return a Double value.
(Yes, “Double”, as opposed to “double”.)
Testing and submitting your code
- We will test your code using ParseTreeDriver.java.
You would be wise to do the same.
- We will not test your code with invalid tokens.
- We will test your code with invalid expressions.
- 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).
- The TAs can help you creating a proper jar file.