Question 1. (25 points) We define the postfix expressions as follows: 1. The low
ID: 3569879 • Letter: Q
Question
Question 1. (25 points) We define the postfix expressions as follows: 1. The lower case letters a, b, c, ... , z are prefix expressions. We call these expressions variables. 2. If E and F are postfix expressions, so is EF+. 3. If E and F are postfix expressions, so is EF*. 4. If E and F are postfix expressions, so is EF-. In the rules 2,3,4, the expressions E and F can be equal or different. Write the method public static BinaryNode buildTheTree(String in) that takes as input a postfix expression and outputs a binary tree whose postorder traversal is the postfix expression. For example, if postfixExp = "abc*+cd-a+-" buildTheTree(postfixExp) should generate the tree from Figure 3. The postorder traversal of this tree is 'a', 'b' , 'c', '*', '+', 'c', 'd', '-', 'a', '+', '-' i.e. the array of characters of the string "abc*+cd-a+-". Throw an illegal argument exception if the input string is not a postfix expression. Write your answer on a blank sheet of paper. Feel free to use helper methods.
Explanation / Answer
public 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;
}
}
public TreeNode root;
public boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
/**
* Constructs an expression tree, using the postfix expression
*/
public void static BinaryNodebuildTheTree(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"); }
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();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.