(35 pts) Implementing Expression Trees: Implement a class called ExpressionTree

Question

(35 pts) Implementing Expression Trees: Implement a class called ExpressionTree . The constructor to ExpressionTree will take in a String that contains a postfix expression. The operands will be integers and the binary operators will be restricted to +, -, *, and divide. Individual tokens, that is the operands and operators, will be delimited by spaces.

So for example: 34 2 - 5 * would mean (34-2)*5.

Your constructor will run the stack based algorithm we discussed in class to build an expression tree. ExpressionNodes will be a nested class within ExpressionTree. You may use any code posted on canvas or from the Weiss textbook as a starting point for this class.

Once you have the ExpressionTree constructed you should provide the following four methods:

public int eval() - this method, when invoked on an expression tree object will return the integer value associated with evaluating the expression tree. It will need to call a private recursive method that takes in the root.

public String postfix() - this method, when invoked on an expression tree object will return a String that contains the corresponding postfix expression. It will need to call a private recursive method that takes in the root.

public String prefix() - this method, when invoked on an expression tree object will return a String that contains the corresponding prefix expression. It will need to call a private recursive method that takes in the root.

public String infix() - this method, when invoked on an expression tree object will return a String that contains the corresponding correct infix expression. Keep in mind that parenthesis will be needed (excessive parenthesis will be tolerated as long as it is correct). It will need to call a private recursive method that takes in the root.

Write a class called Problem1.java that instantiates an expression, and demonstrate your methods.

Explanation / Answer

import java.util.NoSuchElementException;
import java.util.Stack;
class ExpressionTree {

private final String postfix;
private TreeNode root;

/**
* Takes in a valid postfix expression and later its used to construct the expression tree.
* The posfix expression, if invalid, leads to invalid results
*
* @param postfix the postfix expression.
*/
public ExpressionTree(String postfix) {
if (postfix == null) { throw new NullPointerException("The posfix should not be null"); }
if (postfix.length() == 0) { throw new IllegalArgumentException("The postfix should not be empty"); }
this.postfix = postfix;
}

private static class TreeNode {
TreeNode left;
char ch;
TreeNode right;

TreeNode(TreeNode left, char ch, TreeNode right) {
this.left = left;
this.ch = ch;
this.right = right;
}
}

private boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}

/**
* Constructs an expression tree, using the postfix expression
*/
public void createExpressionTree() {
final Stack<TreeNode> nodes = new Stack<TreeNode>();
for (int i = 0; i < postfix.length(); i++) {
char ch = postfix.charAt(i);
if (isOperator(ch)) {
TreeNode rightNode = nodes.pop();
TreeNode leftNode = nodes.pop();
nodes.push(new TreeNode(leftNode, ch, rightNode));
} else {
nodes.add(new TreeNode(null, ch, null));
}
}
root = nodes.pop();
}

/**
* Returns the prefix notation
*
* @return the prefix notation
*/
public String prefix() {
if (root == null) {
throw new NoSuchElementException("The root is empty, the tree has not yet been constructed.");
}

final StringBuilder prefix = new StringBuilder();
preOrder(root, prefix);
return prefix.toString();
}

private void preOrder(TreeNode node, StringBuilder prefix) {
if (node != null) {
prefix.append(node.ch);
preOrder(node.left, prefix);
preOrder(node.right, prefix);
}
}

/**
* Returns the infix expression
*
* @return the string of infix.
*/
public String infix() {
if (root == null) {
throw new NoSuchElementException("The root is empty, the tree has not yet been constructed.");
}
final StringBuilder infix = new StringBuilder();
inOrder(root, infix);
return infix.toString();
}

private void inOrder(TreeNode node, StringBuilder infix) {
if (node != null) {
inOrder(node.left, infix);
infix.append(node.ch);
inOrder(node.right, infix);
}
}

public static void main(String[] args) {
ExpressionTree expressionTree1 = new ExpressionTree("AB*CD/+");
expressionTree1.createExpressionTree();
expressionTree1.prefix();
System.out.println("+*AB/CD: "+expressionTree1.prefix());
System.out.println("A*B+C/D: "+expressionTree1.infix());

ExpressionTree expressionTree2 = new ExpressionTree("ABC+*D/");
expressionTree2.createExpressionTree();
System.out.println("/*A+BCD: "+ expressionTree2.prefix());
System.out.println("A*B+C/D: "+ expressionTree2.infix());

ExpressionTree expressionTree3 = new ExpressionTree("ABCD/+*");
expressionTree3.createExpressionTree();
System.out.println("*A+B/CD :"+ expressionTree3.prefix());
System.out.println("A*B+C/D: "+ expressionTree3.infix());
}
}

/*

output:

+*AB/CD: +*AB/CD
A*B+C/D: A*B+C/D
/*A+BCD: /*A+BCD
A*B+C/D: A*B+C/D
*A+B/CD :*A+B/CD
A*B+C/D: A*B+C/D

*/

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.