Question

Write a program that takes as input a fully parenthesized , arithmetic expression and convert it to a binary expression tree. Your program should display the tree in some way and also print the value associated with the root. LANGUAGE In java

Please answer...

Answer 1

Program:

import java.util.ArrayList;
import java.util.*;

//Stack class
class Stack<T>
{
   //ArratList
   ArrayList<T> stackTop;

   //constructor
   public Stack()
{
stackTop = new ArrayList<>();
}
  
//method to determine whether the stack is empty.
public boolean isEmpty()
{
if(stackTop.isEmpty())
return true;
return false;
}
  
//method to add newItem to the stack.
public void add(T value)
{
stackTop.add(value);
}
  
//method to remove the top element of the stack.
public T pop()
{
if(!isEmpty())
{
        T value = stackTop.get(stackTop.size()-1);
        stackTop.remove(stackTop.size() - 1);
        return value;
}
else
        return null;
}
  
//method to return the top element of the stack.
public T top()
{
   if(!isEmpty())
       return stackTop.get(stackTop.size()-1);
    else
        return null;
}
}

//InfixToPostfix
class InfixToPostfix
{
   //method to return priority of a operator
   public int getPriority(String c)
   {
       switch(c)
       {
           case "^": return 5;
           case "/": return 4;
           case "*": return 3;
           case "+": return 2;
           case "-": return 1;
           case "(": return 0;
          
           default: return 999;
       }
   }
   //check if operator
   boolean isOperator(String s)
   {
       switch(s)
       {
           case "+": case "-": case "/": case "*": case "^":
               return true;
       }
       return false;
   }
  
   //main method
   public String infixToPostfix(String e)
   {
       Stack<String> stk = new Stack();
       String output = "";
      
       stk.add("(");
      
       String exp = e + " )";
      
       String arr[] = exp.split(" ", 20);
      
       //convert from infix to postfix
       for(int i=0; i<arr.length; i++)
       {
           String ch = arr[i];
                                  
           //check for left parenthesis
           if(ch.equals("("))
           {
               stk.add(ch);
           }
           //check for righr parenthesis
           else if(ch.equals(")"))
           {
               while(!stk.top().equals("("))
               {
                   output = output + stk.pop() + " ";
                  
               }
               stk.pop();
           }
           //operator
           else if(isOperator(ch))
           {
               int p1 = getPriority(ch);
      
               int p2 = getPriority(stk.top());
              
               while(p1<=p2)
               {  
                   output = output + stk.pop() + " ";
                   p2 = getPriority(stk.top());
               }
               stk.add(ch);
           }
           //operand
           else
           {
               output = output + ch + " ";
           }
       }
  
      
       if(!stk.isEmpty())
           return "None";
       else
           return output;
   }
}

//Node class
class Node
{
   String info;
   Node lchild;
   Node rchild;
  
   //constructor
   Node(String val)
   {
       info = val;
       lchild = null;
       rchild = null;
   }
}

//ExpressionTree class
class ExpressionTree
{
   //check for operator
   boolean isOperator(String s)
   {
       switch(s)
       {
           case "+": case "-": case "/": case "*": case "^":
               return true;
       }
       return false;
   }
  
   //inorder traversal
   void inorder(Node root)
   {
       if(root!=null)
       {
           inorder(root.lchild);
           System.out.print(root.info + " ");
           inorder(root.rchild);
       }
   }
  
   //expression tree construction
   Node expressionTreeConstruction(String postfix)
   {
       Stack<Node> stk = new Stack();
      
       String arr[] = postfix.split(" ",20);
      
       Node t = null;
      
       for(int i=0; i<arr.length-1; i++)
       {
           t = new Node(arr[i]);
           if(!isOperator(arr[i]))
           {
               stk.add(t);
           }
           else
           {
               Node r = stk.pop();
               Node l = stk.pop();
               t.lchild = l;
               t.rchild = r;
               stk.add(t);
           }
       }

       return stk.pop();
   }
  
   //main method
   public static void main (String[] args)
   {
       Scanner sc = new Scanner(System.in);
      
       System.out.println("Enter the expression: ");
       String infix = sc.nextLine();
      
       InfixToPostfix ip = new InfixToPostfix();
       String postfix = ip.infixToPostfix(infix);
      
       System.out.println("Postfix Expression: " + postfix);
      
       if(postfix.equals("None"))
       {
           System.out.println("Invalid expession");
           return ;
       }
          
       ExpressionTree etree = new ExpressionTree();
       Node root = etree.expressionTreeConstruction(postfix);
      
       System.out.println("Inorder traversal of the Expression Tree: ");
       etree.inorder(root);
   }
}

Output:

Enter the expression:
( a + b ) * ( c - d )
Postfix Expression: a b + c d - *
Inorder traversal of the Expression Tree:
a + b * c - d