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 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; } }
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
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;
}
}
The algorithm of the code is given below:-
- Define a Node class that represents a node in the expression tree.
- Define a Main class that contains methods for parsing prefix, infix, and postfix expressions and converting them to string format.
- In the Node class, define a constructor that takes an element, a left child node, and a right child node as arguments. This constructor initializes the instance variables.
- In the Main class, define a private Node parsePrefix(Scanner input) method that takes a Scanner object as an argument. This method recursively parses a prefix expression and returns the root node of the resulting expression tree.
- In the parsePrefix method, check if the input has no more elements. If so, return null.
- Read the next character from the input.
- If the character is not an operator, create a new node with the character as its element and return it.
- Otherwise, recursively call the parsePrefix method to create the left and right child nodes, then create a new node with the operator as its element and the left and right child nodes as its children.
- In the Main class, define a parseInfix method that takes an infix expression as a string argument. This method uses a stack to parse the expression and returns the root node of the resulting expression tree.
- Create a new Stack object to store nodes.
- Create a Scanner object from the input string and set the delimiter to the empty string.
- While the input has more elements, read the next character.
- If the character is not an operator, create a new node with the character as its element and push it onto the stack.
- Otherwise, pop the top two nodes from the stack and create a new node with the operator as its element and the two nodes as its left and right children. Push the new node onto the stack.
- When there are no more elements in the input, the last node on the stack is the root node of the expression tree.
- In the Main class, define a parsePostfix method that takes a postfix expression as a string argument. This method is similar to the parseInfix method but reads the input from right to left.
- In the Main class, define a toStringPrefix method that returns the prefix string representation of the expression tree.
- In the toStringPrefix method, recursively traverse the expression tree in prefix order and append the element of each node to a string.
- In the Main class, define a toStringInfix method that returns the infix string representation of the expression tree.
- In the toStringInfix method, recursively traverse the expression tree in infix order and append the element of each node to a string.
- In the Main class, define a toStringPostfix method that returns the postfix string representation of the expression tree.
- In the toStringPostfix method, recursively traverse the expression tree in postfix order and append the element of each node to a string.
Trending now
This is a popular solution!
Step by step
Solved in 6 steps with 8 images
