Instructions
Objective
Write a java assignment program to implement tree parsing.
Requirements and Specifications
In this project you will implement an arithmetic expression tree using bridges.base.BinTreeElement as the node. (For more information, check out this tutorial - http://bridgesuncc.github.io/tutorials/BinTree.html) To do so, you will accomplish the following tasks:
- Build a parse tree from a fully parenthesized mathematical expression.
- The method accepts a mathematical expression as a string parameter and returns the root of the parse tree.
- Each token in the mathematical expression is separated by a white-space character, for example, “( ( 7 + 3 ) * ( 5 – 2 ) )”
- The header for this method must be: public static bridges.base.BinTreeElement
buildParseTree(String expression) - Evaluate the expression stored in a parse tree.
- This method evaluates a parse tree by recursively evaluating each subtree.
- The header for this method must be: public static double evaluate(bridges.base.BinTreeElement
tree) - Recover the original mathematical expression from a parse tree.
- The method accepts the root of the parse tree parameter and returns a mathematical expression as a string.
- The header for this method must be: public static String getEquation(bridges.base.BinTreeElement
tree)
The first step in building a parse tree is to break up the expression string into a list of tokens. There are four different kinds of tokens to consider: left parentheses, right parentheses, operators, and operands. Consider the following:
- When we read a left parenthesis, we are starting a new expression, and hence we should create a new tree to correspond to that expression.
- Whenever we read a right parenthesis, we have finished an expression or part of an expression.
- Operands are leaf nodes and children of their operators.
- Every operator is going to have both a left and a right child.
Using the information given above we can define four rules as follows:
- If the current token is a '(', add a new node as the left child of the current node, and descend to the left child.
- If the current token is in the operator list {'+', '-', '/', '*'}, set the root value of the current node to the operator represented by the current token. Add a new node as the right child of the current node and descend to the right child.
- If the current token is a number, set the root value of the current node to the number and return to the parent.
- If the current token is a ')', go to the parent of the current node.
To evaluate a parse tree, we can write an algorithm that evaluates a parse tree by recursively evaluating each subtree.
- Begin the design for the recursive evaluation function by identifying the base case. A natural base case for recursive algorithms that operate on trees is to check for a leaf node. In a parse tree, the leaf nodes will always be operands.
- The recursive step that moves the function toward the base case is to call evaluate on both the left and the right children of the current node.
- To put the results of the two recursive calls together, apply the operator stored in the parent node to the results returned from evaluating both children.
An inorder traversal is needed get the original equation back from the parse tree, remember to add opening and closing parenthesis to retain the meaning of the equation.
Source Code
package cmsc256;
import bridges.base.BinTreeElement;
import bridges.connect.Bridges;
public class Project5 {
public static BinTreeElement buildParseTree(String expression) {
if (expression.startsWith("(") && expression.endsWith(")")) {
String s = expression.substring(1, expression.length() - 1);
String[] ops = split(s);
BinTreeElement data = new BinTreeElement<>(ops[1]);
data.setLeft(buildParseTree(ops[0]));
data.setRight(buildParseTree(ops[2]));
return data;
} else {
return new BinTreeElement<>(expression);
}
}
private static String[] split(String expression) {
int depth = 0;
int index = -1;
for (int i = 0; i < expression.length(); i++) {
if (expression.charAt(i) == '(') {
depth++;
}
if (expression.charAt(i) == ')') {
depth--;
}
if ("+-*/".contains(Character.toString(expression.charAt(i)))) {
if (depth == 0) {
index = i;
break;
}
}
}
if (index < 0) {
throw new IllegalArgumentException();
}
return new String[]{expression.substring(0, index).trim(), Character.toString(expression.charAt(index)),
expression.substring(index + 1).trim()};
}
public static double evaluate(BinTreeElement tree) {
if (tree.getLeft() == null && tree.getRight() == null) {
return Double.parseDouble(tree.getValue());
} else {
double op1 = evaluate(tree.getLeft());
double op2 = evaluate(tree.getRight());
switch (tree.getValue()) {
case "+":
return op1 + op2;
case "-":
return op1 - op2;
case "*":
return op1 * op2;
case "/":
if (op2 == 0.0) {
throw new ArithmeticException();
}
return op1 / op2;
default:
throw new IllegalArgumentException();
}
}
}
public static String getEquation(BinTreeElement tree) {
return getEquationStep(tree).trim();
}
private static String getEquationStep(BinTreeElement node) {
if (node.getLeft() == null && node.getRight() == null) {
return " " + node.getValue() + " ";
} else {
return " (" + getEquationStep(node.getLeft()) + node.getValue() +
getEquationStep(node.getRight()) + ") ";
}
}
public static void main(String[] args) {
String ex1 = "((7 + 3) * (5 - 2))";
BinTreeElement parseTree1 = buildParseTree(ex1);
double answer1 = evaluate(parseTree1);
System.out.println(answer1);
System.out.println(getEquation(parseTree1));
String ex2 = "((10 + 5) * 3)";
BinTreeElement parseTree2 = buildParseTree(ex2);
double answer2 = evaluate(parseTree2);
System.out.println(answer2);
System.out.println(getEquation(parseTree2));
String ex3 = "(((((2 * 12) / 6) + 3) - 17) + (2 * 0))";
BinTreeElement parseTree3 = buildParseTree(ex3);
double answer3 = evaluate(parseTree3);
System.out.println(answer3);
System.out.println(getEquation(parseTree3));
String ex4 = "(3 + (4 * 5))";
BinTreeElement parseTree4 = buildParseTree(ex4);
double answer4 = evaluate(parseTree4);
System.out.println(answer4);
System.out.println(getEquation(parseTree4));
/* Initialize a Bridges connection */
Bridges bridges = new Bridges(5, "username", "appl_Id");
/* Set an assignment title */
bridges.setTitle( "Arithmetic Parse Tree Project -Debra Duke");
bridges.setDescription("CMSC 256, Spring 2022");
try {
/* Tell BRIDGES which data structure to visualize */
bridges.setDataStructure(parseTree1);
/* Visualize the Array */
bridges.visualize();
/* Tell BRIDGES which data structure to visualize */
bridges.setDataStructure(parseTree2);
/* Visualize the Array */
bridges.visualize();
/* Tell BRIDGES which data structure to visualize */
bridges.setDataStructure(parseTree3);
/* Visualize the Array */
bridges.visualize();
/* Tell BRIDGES which data structure to visualize */
bridges.setDataStructure(parseTree4);
/* Visualize the Array */
bridges.visualize();
} catch (Exception ex) {
System.out.println( "Error connecting to Bridges server. ");
}
}