Wanting to make sure I\'m on the right track: (my code is below, but here are th
ID: 3674652 • Letter: W
Question
Wanting to make sure I'm on the right track: (my code is below, but here are the rules I have to follow):
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.
public class ExpressionTree {
public static class ExpressionNode {
char data;
static Character left;
static Character right;
public ExpressionNode(char data) {
this.data = data;
ExpressionNode.left = null;
ExpressionNode.right = null;
}
}
public ExpressionTree(String postfixExp) {
MyStack<Character> s = new MyStack<Character>();
int i = 0, n = postfixExp.length();
char token;
// loop until i reaches the end of the string
while (i != n) {
// skip blanks and tabs in the expression
while (postfixExp.charAt(i) == ' ' || postfixExp.charAt(i) == ' ')
i++;
// if the expression has trailing whitespace ie. the end of the
// String
if (i == n)
break;
// extract the current token and increment i
token = postfixExp.charAt(i);
i++;
// checking to see if the token is an operator or an operand
if (token == '+' || token == '-' || token == '*' || token == '/') {
// current token is an operator: pop to the stack
ExpressionNode.right = s.pop();
ExpressionNode.left = s.pop();
// creating a new subtree with token as root
newNode = new ExpressionNode<Character>(token, ExpressionNode.left, ExpressionNode.right);
s.push(newNode);
} else { // must be an operand
newNode = new ExpressionNodes<Character>(token);
s.push(newNode);
}
}
}
public int eval() {
}
public String postfix() {
}
public String prefix() {
if (node.left != null) {
prefix(node.left);
}
if (node.right != null) {
prefix(node.right);
}
}
public String infix() {
}
}
Explanation / Answer
import java.util.Stack;
import java.util.StringTokenizer;
public class ExpressionTree{
private ExpressionNode root;
private char[] operators = {'+', '-', '*', '/'};
public ExpressionTree(String str)
{
root = strToTree(str);
}
public ExpressionTree(ExpressionNode root)
{
this.root = root;
}
private ExpressionNode strToTree(String s)
{
//Handle nulls? Handle empty expression trees? etc.
Stack<ExpressionNode> st = new Stack<>();
StringTokenizer tk = new StringTokenizer(s);
while(tk.hasMoreTokens())
{
String token = tk.nextToken();
boolean isOperator = false;
for(char operator : operators)
if(token.equals(Character.toString(operator)))
isOperator = true;
ExpressionNode n;
if(isOperator)
n = new ExpressionNode(token.charAt(0));
else
n = new ExpressionNode(Integer.parseInt(token));
if(n.isOperator)
{
ExpressionNode a = st.pop();
ExpressionNode b = st.pop();
n.right = a;
n.left = b;
st.push(n);
}
else
{
st.push(n);
}
}
return st.pop();
}
private static class ExpressionNode
{
public int value;
public char operator;
public boolean isOperator;
public ExpressionNode left;
public ExpressionNode right;
public ExpressionNode(int theElement)
{
value = theElement;
isOperator = false;
}
public ExpressionNode(char theElement)
{
operator = theElement;
isOperator = true;
}
// Only operators have two subtrees/leaves
public ExpressionNode(char theElement, ExpressionNode lt,
ExpressionNode rt)
{
operator = theElement;
isOperator = true;
left = lt;
right = rt;
}
}
private int performOperation(int a, int b, char op)
{
if(op == '+')
return a + b;
else if(op == '-')
return a - b;
else if(op == '*')
return a * b;
else if(op == '/')
return a / b;
else
throw new IllegalArgumentException("Illegal operation performed");
}
// 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 int eval()
{
if(root == null)
return 0;
else
return eval(root);
}
private int eval(ExpressionNode node)
{
int left;
int right;
// base case
if(!node.isOperator)
return node.value;
else
{
left = eval(node.left);
right = eval(node.right);
return performOperation(left, right, node.operator);
}
}
// 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 postfix()
{
return postfix(root);
}
private String postfix(ExpressionNode node)
{
String left = "";
String right = "";
if(!node.isOperator)
return "" + node.value;
else
{
left = postfix(node.left);
right = postfix(node.right);
return left + " " + right + " " + node.operator;
}
}
// 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 prefix()
{
return prefix(root);
}
private String prefix(ExpressionNode node)
{
String left = "";
String right = "";
if(!node.isOperator)
return "" + node.value;
else
{
left = prefix(node.left);
right = prefix(node.right);
return node.operator + " " + left + " " + right;
}
}
// 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.
public String infix()
{
return infix(root);
}
private String infix(ExpressionNode node)
{
String left = "";
String right = "";
if(!node.isOperator)
return "" + node.value;
else
{
left = infix(node.left);
right = infix(node.right);
return "(" + left + " " + node.operator + " " + right + ")";
}
}
public static void main(String[] args)
{
ExpressionTree t = new ExpressionTree("3 5 4 * + 8 4 * 3 + 2 * +");
System.out.println(t.eval());
System.out.println("Postfix: " + t.postfix());
System.out.println("Prefix: " + t.prefix());
System.out.println("Infix: " + t.infix());
}
}
output
93
Postfix: 3 5 4 * + 8 4 * 3 + 2 * +
Prefix: + + 3 * 5 4 * + * 8 4 3 2
Infix: ((3 + (5 * 4)) + (((8 * 4) + 3) * 2))
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.