Implement a class ExprTree for representing expression trees , including: The op

Question

Implement a class ExprTree for representing expression trees, including:

The operations to build an expression tree from a postfix arithmetic expression.

A recursive function to “evaluate” a non-empty expression tree using these rules:

If the tree has only one node (which must be a leaf), then the evaluation of the tree returns the real number (type double) that is the node’s entry.

If the tree has more than one node, and the root contains an “operator” (+, -, *, /), then first evaluate the left subtree, then the right subtree, and apply the “operator” on these two values to get result.

For example, consider the following expression tree (with real numbers in parenthesis and operators in square bracket). The left subtree evaluates to 3+7, which is 10. The right subtree evaluates to 14. So the entire tree evaluates to 10*14 which is 140.

For example, consider the above expression tree (with real numbers in parenthesis and operators in square bracket). The left subtree evaluates to 3+7, which is 10. The right subtree evaluates to 14. So the entire tree evaluates to 10*14 which is 140.

Explanation / Answer

import java.util.Scanner;
class ExpressionTree
{
class TreeNode
{
char data;
TreeNode left, right;

/** constructor **/
public TreeNode(char data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class StackNode
{
TreeNode treeNode;
StackNode next;
public StackNode(TreeNode treeNode)
{
this.treeNode = treeNode;
next = null;
}
}

private static StackNode top;
public ExpressionTree()
{
top = null;
}
public void clear()
{
top = null;
}
private void push(TreeNode ptr)
{
if (top == null)
top = new StackNode(ptr);
else
{
StackNode nptr = new StackNode(ptr);
nptr.next = top;
top = nptr;
}
}
private TreeNode pop()
{
if (top == null)
throw new RuntimeException("Underflow");
else
{
TreeNode ptr = top.treeNode;
top = top.next;
return ptr;
}
}
private TreeNode peek()
{
return top.treeNode;
}
private void insert(char val)
{
try
{
if (isDigit(val))
{
TreeNode nptr = new TreeNode(val);
push(nptr);
}
else if (isOperator(val))
{
TreeNode nptr = new TreeNode(val);
nptr.left = pop();
nptr.right = pop();
push(nptr);
}
}
catch (Exception e)
{
System.out.println("Invalid Expression");
}
}

private boolean isDigit(char ch)
{
return ch >= '0' && ch <= '9';
}

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

private int toDigit(char ch)
{
return ch - '0';
}

public void buildTree(String eqn)
{
for (int i = eqn.length() - 1; i >= 0; i--)
insert(eqn.charAt(i));
}

public double evaluate()
{
return evaluate(peek());
}

public double evaluate(TreeNode ptr)
{
if (ptr.left == null && ptr.right == null)
return toDigit(ptr.data);
else
{
double result = 0.0;
double left = evaluate(ptr.left);
double right = evaluate(ptr.right);
char operator = ptr.data;

switch (operator)
{
case '+' : result = left + right; break;
case '-' : result = left - right; break;
case '*' : result = left * right; break;
case '/' : result = left / right; break;
default : result = left + right; break;
}
return result;
}
}

}

/** class ExpressionTreeTest **/
public class ExpressionTreeTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Expression Tree Test");

/** make object of ExpressionTree **/
ExpressionTree et = new ExpressionTree();

System.out.println(" Enter equation in prefix form");
et.buildTree(scan.next());

System.out.print("Input : ");
  
System.out.println(" Evaluated Result : "+ et.evaluate());
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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