(JAVA) Implementing Expression Trees: Implement a class called ExpressionTree .
ID: 3869450 • Letter: #
Question
(JAVA) 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:
1. 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.
2. 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.
3. 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.
4. 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.
Explanation / Answer
package Online;
import java.util.Scanner;
//ExpressionTree class definition
class ExpressionTree
{
//Nested class TreeNode definition
class TreeNode
{
char value;
TreeNode left, right;
//Parameterized constructor
public TreeNode(char value)
{
this.value= value;
this.left = null;
this.right = null;
}//End of constructor
}//End of class
//Nested class StackNode definition
class StackNode
{
//Creates an object of class TreeNode
TreeNode tempNode;
//Self referential object of class StackNode
StackNode next;
//Parameterized constructor which takes TreeNode object as a parameter
public StackNode(TreeNode tempNode)
{
this.tempNode = tempNode;
next = null;
}//End of constructor
}//End of class
//StackNode object to point to top of the stack
//Declared as a instance variable of class ExpressionTree
private static StackNode stackTop;
//Default constructor
public ExpressionTree()
{
stackTop = null;
}//End of constructor
//Method to clear the stack
public void clear()
{
stackTop = null;
}//End of method
//Method to push a node to the stack
//Takes TreeNode object as a parameter
private void push(TreeNode ptr)
{
//Checks if the stack is empty
if (stackTop == null)
//Initializes the TreeNode object with the help of StackNode constructor and assigns it to top, which is an object of StackNode
stackTop = new StackNode(ptr);
//If it is not empty
else
{
//Calls the StackNode parameterized constructor to initialize StackNode object tempPtr
StackNode tempPtr = new StackNode(ptr);
//StackNode object tempPtr next is pointing to top
tempPtr.next = stackTop;
//tempPtr is assigned to top
stackTop = tempPtr;
}//End of else
}//End of push method
//Method to pop an element from the stack
private TreeNode pop()
{
//Checks if the stack is empty
if (stackTop == null)
//Throws an runtime exception
throw new RuntimeException("Underflow");
//If it is not empty
else
{
//Extract the node at the top and assigns it to ptr object of TreeNode
TreeNode ptr = stackTop.tempNode;
//top is assigned with next node
stackTop = stackTop.next;
//returns the node
return ptr;
}//End of else
}//End of pop method
//Method to return the top node
private TreeNode peek()
{
return stackTop.tempNode;
}//End of method
//Method to insert a value
private void insert(char val)
{
//Try block begins
try
{
//Checks whether the character is a digit or not
if (isDigit(val))
{
//Stores the val in the instance variable value of TreeNode using constructor
TreeNode currentPtr = new TreeNode(val);
//push the node to the stack
push(currentPtr);
}//End of if
//Checks whether the character is a operator
else if (isOperator(val))
{
//Stores the val in the instance variable value of TreeNode using constructor
TreeNode currentPtr = new TreeNode(val);
//Extract both the operand of the operator from the stack
//Extracts the top node from the stack and adds it the left of the TreeNode
currentPtr.left = pop();
//Extracts the top node from the stack and adds it the right of the TreeNode
currentPtr.right = pop();
//Push the node to the stack
push(currentPtr);
}//End of else if
}//End of try
//Catch block to handle exception
catch (Exception exp)
{
System.out.println("Invalid Expression");
}//End of catch
}//End of method
//Method to check whether the parameter is digit or not
private boolean isDigit(char data)
{
//Returns true if the character is between 0 and 9 including both otherwise returns false
return data >= '0' && data <= '9';
}//End of method
//Method to check whether the parameter is operator or not
private boolean isOperator(char data)
{
//Returns true if the character is either +, -, *, / otherwise returns false
return data == '+' || data == '-' || data == '*' || data == '/';
}//End of method
//Converts character to number
private int toDigit(char data)
{
return data - '0';
}//End of method
//Method to construct a tree
public void buildTree(String equation)
{
//Loops from equation length minus one to starting position of equation in reverse order
for (int c = equation.length() - 1; c >= 0; c--)
{
//Extracts a character at c index position from the equation and insert it
insert(equation.charAt(c));
}//End of loop
}//End of method
//Method to evaluate the expression
public double evaluateExpression()
{
//Extracts to top node from the stack and returns it
return evaluateExpression(peek());
}//End of method
//Takes TreeNode object as a parameter to evaluate an expression
public double evaluateExpression(TreeNode temp)
{
//Checks whether the left and right of the tree is null or not
if (temp.left == null && temp.right == null)
//Calls the method toDigit() to convert the data to integer
return toDigit(temp.value);
//If left and right or the tree is not null
else
{
//To store the result
double finalResult = 0.0;
//Extract the left node of the tree for evaluation
double left = evaluateExpression(temp.left);
//Extract the right node of the tree for evaluation
double right = evaluateExpression(temp.right);
//Extracts the operator
char operator = temp.value;
//Checks the operator
switch (operator)
{
//Addition operation
case '+' :
finalResult = left + right;
break;
//Subtraction operation
case '-' :
finalResult = left - right;
break;
//Multiplication operation
case '*' :
finalResult = left * right;
break;
//Division operation
case '/' :
finalResult = left / right;
break;
//If none of the above case satisfies
default :
finalResult = left + right;
break;
}//End of switch
//Returns the result
return finalResult;
}//End of else
}//End of method
//Converts to postfix
public void postfix()
{
//Calls the postOrder method by peeking the top element from the stack
convertPostFix(peek());
}//End of method
//Recursively call the method to display postfix expression
private void convertPostFix(TreeNode temp)
{
//Checks for not empty
if (temp != null)
{
//Calls recursively for node left
convertPostFix(temp.left);
//Calls recursively for node right
convertPostFix(temp.right);
//Displays the value
System.out.print(temp.value);
}//End of if
}//End of method
//Method to convert to infix
public void infix()
{
//Calls the method by passing the top of the stack
convertInfix(peek());
}//End of method
//Recursively calls the method to display infix form
private void convertInfix(TreeNode temp)
{
//Checks for not empty
if (temp != null)
{
//Calls recursively for node left
convertInfix(temp.left);
//Displays the value
System.out.print(temp.value);
//Calls recursively for node right
convertInfix(temp.right);
}//End of if
}//End of method
//Method to convert to prefix
public void prefix()
{
//Calls the method by passing the top of the stack
convertPrefix(peek());
}//End of method
//Recursively calls the method to display the preorder form
private void convertPrefix(TreeNode temp)
{
//Checks for not null
if (temp != null)
{
//Displays the data
System.out.print(temp.value);
//Calls recursively for node left
convertPrefix(temp.left);
//Calls recursively for node right
convertPrefix(temp.right);
}//End of if
}//End of method
}//End of class
//Driver class
public class ExpressionTreeTest
{
//Main method definition
public static void main(String[] args)
{
//Scanner class object created to accept the expression
Scanner input = new Scanner(System.in);
System.out.println("Expression Tree Test");
//Creates an object of the expression tree
ExpressionTree expTree = new ExpressionTree();
//Accepts the expression
System.out.println(" Enter equation in prefix form");
expTree.buildTree(input.next());
//Displays in Infix form
System.out.print(" Infix : ");
expTree.infix();
//Displays in Prefix form
System.out.print(" Prefix : ");
expTree.prefix();
//Displays in Postfix form
System.out.print(" Postfix : ");
expTree.postfix();
//Displays the evaluated expression result
System.out.println(" Evaluated Result : "+ expTree.evaluateExpression());
input.close();
}//End of main
}//End of class
Sample Run:
Expression Tree Test
Enter equation in prefix form
+-+3*/465/34*/123
Infix : 3+4/6*5-3/4+1/2*3
Prefix : +-+3*/465/34*/123
Postfix : 346/5*+34/-12/3*+
Evaluated Result : 7.083333333333333
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.