Question

Create a program using Binary Trees in Java to do the following

1. Verify a given expression is balanced in regards to parentheses

2. covert an infix expression to a postfix expression

3. Evaluate the expression

Given expressions:

String s[] = {"5 + ) * ( 2",
" 2 + ( - 3 * 5 ) ",
"(( 2 + 3 ) * 5 ) * 8 ",
"5 * 10 + ( 15 - 20 ) ) - 25",
" 5 + ( 5 * 10 + ( 15 - 20 ) - 25 ) * 9"
};

a given expression could result in one of the following:

Mismatch parentheses
Too many operators, or too many operands in which case the expression would not have been written properly in the first place
The result is assumed to be correct.

Answer 1

package expressiontree.java;

public class ExpressionTree {
String data;
ExpressionTree left;
ExpressionTree right;
boolean bracmismatch;
boolean opermismatch;
ExpressionTree()
{
data="";
left=null;
right=null;
bracmismatch=false;
opermismatch=false;
  
}
ExpressionTree(String val)
{
data=val;
left=null;
right=null;
bracmismatch=false;
opermismatch=false;
  
}
boolean isOperator(char ch)
{
String operators="+-/*%";
return operators.indexOf(ch)>-1;
}
ExpressionTree NodeInsert(String exp)
{
  
ExpressionTree node=new ExpressionTree();
String operand="";
node.left=null;
node.right=null;
int brac_count;
int i;
for(i=0;i<exp.length();i++)
{
if(isOperator(exp.charAt(i)))
{
if((i>=0)&&((i+1)<exp.length()))
{
  
node.left=NodeInsert(exp.substring(0,i));
operand=""+exp.charAt(i);
  
  
//IF NEGATIVE VALUES ARE ACCEPTED
if((node.left==null)&&(operand.equals("-")))
{
i=i+1;
while((i<exp.length())&&(!isOperator(exp.charAt(i))))
{
operand+=exp.charAt(i);
i++;
}
  
node.left=new ExpressionTree(operand);
if(i<exp.length())
{
operand=""+exp.charAt(i);
node.right=NodeInsert(exp.substring(i+1));
}
  
}
else
{
node.right=NodeInsert(exp.substring(i+1));
}
  
//IF ONLY POSITIVE VALUES ARE ACCEPTED
/*

node.right=NodeInsert(exp.substring(i+1));

if((node.left==null)||(node.right==null))
{
  
node.opermismatch=true;
  
}*/
  
//IF NEGATIVE VALUES ARE ACCEPTED
if(((node.left==null)||(node.right==null))&&(!operand.equals("-")))
{
node.opermismatch=true;
}
if((node.right==null)&&(operand.equals("-")))
{
node.opermismatch=true;
  
}
  
  
break;
}
  
}
else if(exp.charAt(i)=='(')
{
brac_count=1;
int j=i+1;
while(j<exp.length()&&(brac_count>0))
{
if((exp.charAt(j)=='('))
{
brac_count++;
}
else if(((exp.charAt(j)==')')))
{
brac_count--;
}
j++;
}   
if((i==0)&&(j==exp.length()))
{
exp=exp.substring(i+1,j-1);
return (NodeInsert(exp));
}
if(j==exp.length())
node.bracmismatch=true;
i=j-1;
}
else if(exp.charAt(i)==')')
{
node.bracmismatch=true;
}
  
else
operand=operand+exp.charAt(i);
  
}
if("".equals(operand))return null;
node.data=operand;
return node;
}
void printPost(ExpressionTree head)
{
if(head.left!=null)
printPost(head.left);
if(head.right!=null)
printPost(head.right);
  
System.out.print(head.data+"\t");
}
boolean checkOper(ExpressionTree head)
{
boolean flag=false;
if(head.opermismatch==true)
{
return head.opermismatch;
}
if(head.left!=null)
{
flag=checkOper(head.left);
}
if(flag==true)
{
return flag;
}
if(head.right!=null)
{
flag=checkOper(head.right);
}
  
return flag;
}
boolean checkBrac(ExpressionTree head)
{
boolean flag=false;
if(head.bracmismatch==true)
{
return head.bracmismatch;
}
if(head.left!=null)
{
flag=checkBrac(head.left);
}
if(flag==true)
{
return flag;
}
if(head.right!=null)
{
flag=checkBrac(head.right);
}
  
return flag;
}
public static void main(String[] args) {

String s[] = {"5+)*(2","2+(-3*5)","((2+3)*5)*8","5*10+(15-20))-25","5+(5*10+(15-20)-25)*9"};
for (String expression : s) {
System.out.println(expression);
ExpressionTree exptree=new ExpressionTree();
exptree=exptree.NodeInsert(expression);
if(exptree.checkBrac(exptree))
{
System.out.println("Mismatch parentheses");
}
else if(exptree.checkOper(exptree))
{
System.out.println("Too many operators, or too many operands in which case the expression would not have been written properly in the first place");
}
else
{
System.out.print("The result is assumed to be correct.");
exptree.printPost(exptree);
System.out.println();
}
}

}
  
}

OUTPUT:(Neg values accepted)

OUTPUT:(Neg values not accepted)

With Evaluation:

package expressiontree;

import java.util.Stack;
import javafx.util.Pair;

public class ExpressionTree {
String data;
ExpressionTree left;
ExpressionTree right;
boolean bracmismatch;
boolean opermismatch;
static Stack<Integer> stack=new Stack<>();
static Pair prec[]=new Pair[5];
ExpressionTree()
{
data="";
left=null;
right=null;
bracmismatch=false;
opermismatch=false;
prec[0]=new Pair('+',0);
prec[1]=new Pair('-',0);
prec[2]=new Pair('*',1);
prec[3]=new Pair('/',1);
  
}
static int getVal(char c)
{
int val=-1;
for(int i=0;i<4;i++)
{
if((char)prec[i].getKey()==c)
{
val=(int)prec[i].getValue();
break;
}
}
return val;
}
ExpressionTree(String val)
{
data=val;
left=null;
right=null;
bracmismatch=false;
opermismatch=false;
  
}
boolean isOperator(char ch)
{
String operators="+-/*%";
return operators.indexOf(ch)>-1;
}
ExpressionTree NodeInsert(String exp,int prec)
{
  
ExpressionTree node=new ExpressionTree();
String operand="";
node.left=null;
node.right=null;
int brac_count;
int i;
  
for(i=0;i<exp.length();i++)
{

if(isOperator(exp.charAt(i))&&(prec<=getVal(exp.charAt(i))))
{
if((i>=0)&&((i+1)<exp.length()))
{

node.left=NodeInsert(exp.substring(0,i),0);
operand=""+exp.charAt(i);
  
  
/*//IF NEGATIVE VALUES ARE ACCEPTED
if((node.left==null)&&(operand.equals("-")))
{
i=i+1;
while((i<exp.length())&&(!isOperator(exp.charAt(i))))
{
operand+=exp.charAt(i);
i++;
}
  
node.left=new ExpressionTree(operand);
if(i<exp.length())
{
operand=""+exp.charAt(i);
node.right=NodeInsert(exp.substring(i+1));
}
  
}
else
{
node.right=NodeInsert(exp.substring(i+1));
}*/
  
//IF ONLY POSITIVE VALUES ARE ACCEPTED
//System.out.println(exp.substring(i+1));
node.right=NodeInsert(exp.substring(i+1),getVal(exp.charAt(i)));
if((node.left==null)||(node.right==null))
{
  
node.opermismatch=true;
  
}
  
if(getVal(exp.charAt(i))==1){

  
i++;
while((!isOperator(exp.charAt(i)))&&(i+1<exp.length())&&(exp.charAt(i)!=')'))
{
i++;
  
}
  
if(i+1!=exp.length())
{
ExpressionTree innernode=new ExpressionTree();
innernode.left=node ;
node.data=operand;
innernode.right=NodeInsert(exp.substring(i+1),0);
node=innernode;
operand=""+exp.charAt(i);
}
}
  
/*//IF NEGATIVE VALUES ARE ACCEPTED
if(((node.left==null)||(node.right==null))&&(!operand.equals("-")))
{
node.opermismatch=true;
}
if((node.right==null)&&(operand.equals("-")))
{
node.opermismatch=true;
  
}*/
  
  
break;
}
  
}
else if(exp.charAt(i)=='(')
{
brac_count=1;
int j=i+1;
while(j<exp.length()&&(brac_count>0))
{
if((exp.charAt(j)=='('))
{
brac_count++;
}
else if(((exp.charAt(j)==')')))
{
brac_count--;
}
j++;
}   
if((i==0)&&(j==exp.length()))
{
exp=exp.substring(i+1,j-1);
return (NodeInsert(exp,0));
}
if(j==exp.length())
node.bracmismatch=true;
i=j-1;
}
else if(exp.charAt(i)==')')
{
node.bracmismatch=true;
}
else if(isOperator(exp.charAt(i))&&(prec>getVal(exp.charAt(i))))
{
return NodeInsert(exp.substring(0,i),0);
}
else
operand=operand+exp.charAt(i);
  
}
if("".equals(operand))return null;
node.data=operand;
return node;
}
void printPost(ExpressionTree head)
{
if(head.left!=null)
printPost(head.left);
if(head.right!=null)
printPost(head.right);
try{
stack.push(Integer.parseInt(head.data));
}
catch(Exception e)
{

int v1 = stack.pop();
int v2 = stack.pop();
  
switch(head.data)
{
case "+":
stack.push(v2+v1);
break;
  
case "-":
stack.push(v2- v1);
break;
  
case "/":
stack.push(v2/v1);
break;
  
case "*":
stack.push(v2*v1);
break;
}
  
}
System.out.print(head.data+"\t");
}
  
boolean checkOper(ExpressionTree head)
{
boolean flag=false;
if(head.opermismatch==true)
{
return head.opermismatch;
}
if(head.left!=null)
{
flag=checkOper(head.left);
}
if(flag==true)
{
return flag;
}
if(head.right!=null)
{
flag=checkOper(head.right);
}
  
return flag;
}
boolean checkBrac(ExpressionTree head)
{
boolean flag=false;
if(head.bracmismatch==true)
{
return head.bracmismatch;
}
if(head.left!=null)
{
flag=checkBrac(head.left);
}
if(flag==true)
{
return flag;
}
if(head.right!=null)
{
flag=checkBrac(head.right);
}
  
return flag;
}
public static void main(String[] args) {

String s[] = {"5+)*(2","2+(-3*5)","((2+3)*5)*8","5*10+(15-20))-25","5+(5*10+(15-20)-25)*9"};
for (String expression : s) {
System.out.println(expression);
ExpressionTree exptree=new ExpressionTree();
exptree=exptree.NodeInsert(expression,0);
if(exptree.checkBrac(exptree))
{
System.out.println("Mismatch parentheses");
}
else if(exptree.checkOper(exptree))
{
System.out.println("Too many operators, or too many operands in which case the expression would not have been written properly in the first place");
}
else
{
System.out.print("The result is assumed to be correct.");
exptree.printPost(exptree);
System.out.println();
System.out.println("Result : "+stack.pop());
}
}

}
  
}