Java Expression Trees **This has to be written using the Tree data structure!**

Question

Java Expression Trees

**This has to be written using the Tree data structure!**

For this assignment you will write a program using and Expression Tree that reads postfix expression from the user, one per line, then converts the postfix expression to infix, gets the numeric value of the expression, and terminates when the user enters a blank line.

For each postfix expression, due the following:

1. Build an expression tree supporting +-*/
2. Print out the equivalent infix expression, in heavily parenthesesed form. 3. Print out the numeric value of the expression.

3. Print out the numeric value of the expression.

Make sure your main method is in a class called ETreeDriver. Do not print any prompts or values other than the infix expression and resulting value.

Explanation / Answer

//Java program to construct an expression tree

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

//Java program for expression tree
class TreeNode {

   char value;
   TreeNode left, right;

   TreeNode(char item) {
       value = item;
       left = right = null;
   }
}

class ExpressionTree {

   // A utility function to check if 'c'
   // is an operator
   boolean isOperator(char c) {
       if (c == '+' || c == '-' || c == '*' || c == '/') {
           return true;
       }
       return false;
   }

   // Utility function to do inorder traversal
   void inorder(TreeNode t) {
       if (t != null) {
           inorder(t.left);
           System.out.print(t.value + " ");
           inorder(t.right);
       }
   }

   // Returns root of constructed tree for given
   // postfix expression
   TreeNode constructTree(char postfix[]) {
       Stack<TreeNode> st = new Stack();
       TreeNode 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 TreeNode(postfix[i]);
               st.push(t);
           } else // operator
           {
               t = new TreeNode(postfix[i]);

               // Pop two top TreeNodes
               // Store top
               t1 = st.pop();      // Remove top
               t2 = st.pop();

               // make them children
               t.right = t1;
               t.left = t2;

               // System.out.println(t1 + "" + t2);
               // Add this subexpression to stack
               st.push(t);
           }
       }

       // only element will be root of expression
       // tree
       t = st.peek();
       st.pop();

       return t;
   }
   /**
   * Converts any postfix to infix
   * @param postfix String expression to be converted
   * @return String infix expression produced
   */
   public String convert(String postfix){
       Stack<String> s = new Stack<>();

       for(int i = 0; i < postfix.length(); i++){
           char c = postfix.charAt(i);
           if(isOperator(c)){
               String b = s.pop();
               String a = s.pop();
               s.push("("+a+c+b+")");
           }
           else
               s.push(""+c);
       }

       return s.pop();
   }
   //function to evaluate a postfix expression
   public int evaluate(String s)
   {
       int n,r=0;
       n=s.length();
       Stack<Integer> a = new Stack<>();
       for(int i=0;i<n;i++)
       {
           char ch=s.charAt(i);
           if(ch>='0'&&ch<='9')
               a.push((int)(ch-'0'));
           else if(ch == ' ')
               continue;
           else
           {
               int x=a.pop();
               int y=a.pop();
               switch(ch)
               {
               case '+':r=x+y;
               break;
               case '-':r=y-x;
               break;
               case '*':r=x*y;
               break;
               case '/':r=y/x;
               break;
               default:r=0;
               }
               a.push(r);
           }
       }
       r=a.pop();
       return(r);
   }

   // to read input string
   public static String getString()throws IOException
   {
       InputStreamReader isr = new InputStreamReader(System.in);
       BufferedReader br = new BufferedReader(isr);
       String s = br.readLine();
       return s;
   }
   public static void main(String args[]) throws IOException {

       String input;
       ExpressionTree et = new ExpressionTree();
       TreeNode root;
       while(true)
       {
           System.out.println("Enter the postfix expresion(of enter to stop)");
           input=getString();
           if(input.equals(""))
               break;
           char[] charArray = input.toCharArray();
           root = et.constructTree(charArray);
           System.out.print("infix expression is : ");
           //et.inorder(root);
           System.out.println(et.convert(input));
           System.out.println("Expression value: "+et.evaluate(input));
       }
   }
}

/*

Output:

Enter the postfix expresion(of enter to stop)
36+48*9*-
infix expression is : ((3+6)-((4*8)*9))
Expression value: -279
Enter the postfix expresion(of enter to stop)

*/

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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