In Java,

Complete the incomplete method of ExpressionTree.java. The incomplete methods are

private Node parsePrefix(Scanner input) // Required

public void parseInfix(String string) // Optional

public void parsePostfix(String string) // Optional

Implementations of parseInfix and parsePostfix require use of a stack. Implementation of parsePrefix does not.

Read all of the ExpressionTree.java file before starting your implementation, so that you see the helper methods that are provided and get an idea of the context for your implementation. Although not needed for your implementation, you should be sure you understand how the toStringPrefix, toStringInfix, and toStringPostfix methods work.

Note:

The main() method accepts a single String as its argument. The String should be a prefix, infix, or postfix mathematical expression with no characters other than operators (+, -, *, and /) and operands (single characters a-z).

As written, the main() method calls parsePrefix() to create an expression tree from a prefix expression.

The main() method then prints the expression tree in prefix, infix, and postfix order, yielding prefix, infix, and postfix expressions that represent the same calculation.

Given the (prefix expression) argument "*-ab+cd", the main() method should print

input = *-ab+cd prefix = *-ab+cd infix = a-b*c+d postfix = ab-cd+*

ExpressionTree.java

/** * ExpressionTree provides methods to parse a prefix expression, infix expresseion, or postfix expression. * In addition, there are methods for returning a parsed expression as a prefix expression, infix expresseion, or postfix expression. * Assumptions: * - Expressions consist of single character variable names and the operators +, -, *, /, and %. * - Expressions do not contain parentheses. * - Expressions do not contain whitespace. * @author (your name) * @version (a version number or a date) */ import java.util.Scanner; import java.util.Stack; // Needed for parseInfix and parsePostfix

public class ExpressionTree { public class Node { char element; Node left, right; public Node(char element) { this.element = element; this.left = null; this.right = null; } public Node(char element, Node left, Node right) { this.element = element; this.left = left; this.right = right; } } private Node root; public static void main(String[] args) { ExpressionTree expressionTree = new ExpressionTree(); String expression = "*-ab+cd"; if (args.length != 0) { expression = args[0]; } System.out.println(" input = " + expression); expressionTree.parsePrefix(expression); System.out.println(" prefix = " + expressionTree.toStringPrefix()); System.out.println(" infix = " + expressionTree.toStringInfix()); System.out.println("postfix = " + expressionTree.toStringPostfix()); } /** * Sets root to the root of the expression tree. * @param string is a prefix expression to be parsed. */ public void parsePrefix(String string) { Scanner input = new Scanner(string); input.useDelimiter(""); // Each token returned is a single character string root = parsePrefix(input); }

/** * @param input is the sequence of single character strings (a prefix expression) to be parsed. * @return the root node of the expression tree for the input */ private Node parsePrefix(Scanner input) { // Implement this recursive method } /** * Sets root to the root of the expression tree. * @param string is an infix expression to be parsed. */ public void parseInfix(String string) { // Optional implementation. Note: Use the Java Stack class. } /** * Sets root to the root of the expression tree. * @param string is a postfix expression to be parsed. */ public void parsePostfix(String string) { // Optional implementation. Note: Use the Java Stack class. } private Boolean isOperator(char aChar) { return "+-*/^%".contains(Character.toString(aChar)); } public String toStringPrefix() { return toStringPrefix(root); } private String toStringPrefix(Node node) { String result = ""; if (node == null) { return result; } result += String.valueOf(node.element); result += toStringPrefix(node.left); result += toStringPrefix(node.right); return result; } public String toStringInfix() { return toStringInfix(root); } private String toStringInfix(Node node) { String result = ""; if (node == null) { return result; } result += toStringInfix(node.left); result += String.valueOf(node.element); result += toStringInfix(node.right); return result; } public String toStringPostfix() { return toStringPostfix(root); } private String toStringPostfix(Node node) { String result = ""; if (node == null) { return result; } result += toStringPostfix(node.left); result += toStringPostfix(node.right); result += String.valueOf(node.element); return result; } }