Project: Expression Trees IN JAVA This project is adapted from Project 1 of Chap
ID: 3904601 • Letter: P
Question
Project: Expression Trees IN JAVA This project is adapted from Project 1 of Chapter 9 of the textbook. It deals with a simple kind of expression trees, in which there are two kinds of nodes: (a) Leaf nodes, which contain a real number as their clement; and (b) Non-leaf nodes, which have exactly two children and contain one of these characters as their element: +, -, * and /. These characters represent arithmetic operations and have usual interpretations. Implement a class for expression trees with these operations: (a) A constructor that builds an expression tree. It accepts a String that represents a grammatically correct expression as its sole input. Hint: refer to Chapter 6.2 and slides on evaluating expressions. (b) A recursive method named eval that evaluates a non-empty expression tree using these rules: i. If the tree has only one node (which must be a leaf), then eval returns the real number that is the node's clement; ii. If the tree has more than one node and the root contains op where op is one of +, -, * and /, then eval first evaluates the sub-trees of the root and returns the real number obtained by performing operation op on the results from evaluating the sub-trees. (c) A recursive method named infix that output the expression represented by a non-empty expression tree to a String in infix format. (d) A recursive method named postfix that outputs the expression represented by a non-empty expression tree in postfix format. You also need to write another class that applies the operations of the above class.
Explanation / Answer
The code is as follows:
import java.io.*;
import java.util.*;
class Node { //Each node of the expression tree
char value;
Node left, right;
Node(char item) {
value = item;
left = right = null;
}
}
class ExpressionTree { //class to represent expression tree
Node root;
public ExpressionTree(String inFixExp) {
//convert infix expression to postfix first
String pfix = infixToPostfix(inFixExp);
//convert the postfix String to charArray
char [] postfix=pfix.toCharArray();
Stack<Node> st = new Stack(); //internal Stack class used
Node t, t1, t2;
// Traverse through every character of
// input expression
for (int i = 0; i < postfix.length; i++) {
// If operand, simply push into stack
if (!isOperator(postfix[i])) {
t = new Node(postfix[i]);
st.push(t);
} else // operator
{
t = new Node(postfix[i]);
// Pop two top nodes
// Store top
t1 = st.pop();
t2 = st.pop();
// make them children
t.right = t1;
t.left = t2;
// Add this subexpression to stack
st.push(t);
}
}
// only element will be root of expression tree
t = st.peek();
st.pop();
root=t;
}
public void infix(){
inorder(root);
}
public void postfix(){
postorder(root);
}
public void evaluate(){
int result = eval(root);
System.out.println(result);
}
private int eval(Node root)
{
// empty tree
if (root == null)
return 0;
// leaf node i.e, an integer
if (root.left==null && root.right==null)
return (int)(root.value-'0');
// Evaluate left subtree
int l_val = eval(root.left);
// Evaluate right subtree
int r_val = eval(root.right);
// Check which operator to apply
if (root.value=='+')
return l_val+r_val;
if (root.value=='-')
return l_val-r_val;
if (root.value=='*')
return l_val*r_val;
return l_val/r_val;
}
// Utility function to do inorder traversal
private void inorder(Node root) {
if (root != null) {
inorder(root.left);
System.out.print(root.value + " ");
inorder(root.right);
}
}
// Utility function to do postorder traversal
private void postorder(Node root) {
if (root != null) {
inorder(root.left);
inorder(root.right);
System.out.print(root.value + " ");
}
}
//utility function to check operator precedence
private int Prec(char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
//utility function to convert infix expression to postfix
private String infixToPostfix(String exp)
{
// initializing empty String for result
String result = new String("");
// initializing empty stack
Stack<Character> stack = new Stack<>();
for (int i = 0; i<exp.length(); ++i)
{
char c = exp.charAt(i);
// If the scanned character is an operand, add it to output.
if (Character.isLetterOrDigit(c))
result += c;
// If the scanned character is an '(', push it to the stack.
else if (c == '(')
stack.push(c);
// If the scanned character is an ')', pop and output from the stack
// until an '(' is encountered.
else if (c == ')')
{
while (!stack.isEmpty() && stack.peek() != '(')
result += stack.pop();
if (!stack.isEmpty() && stack.peek() != '(')
return "Invalid Expression"; // invalid expression
else
stack.pop();
}
else // an operator is encountered
{
while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek()))
result += stack.pop();
stack.push(c);
}
}
// pop all the operators from the stack
while (!stack.isEmpty())
result += stack.pop();
return result;
}
// A utility function to check if 'c' is an operator
boolean isOperator(char c) {
if (c == '+' || c == '-'
|| c == '*' || c == '/'
|| c == '^') {
return true;
}
return false;
}
public static void main(String args[]) {
Scanner sc=new Scanner(System.in);
System.out.println("Enter expression: ");
String exp = sc.nextLine();
ExpressionTree et = new ExpressionTree(exp);
System.out.println("The infix expression is:");
et.infix();
System.out.println(" The postfix expression is:");
et.postfix();
System.out.println(" The result of the expression is:");
et.evaluate();
}
}
Sample Output:
radas-macOS:Desktop radas$ java ExpressionTree
Enter expression:
2+5*3-4
The infix expression is:
2 + 5 * 3 - 4
The postfix expression is:
2 + 5 * 3 4 -
The result of the expression is:
13
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.