In: Computer Science
In assignment 1 you had used the data structure called Stack to evaluate arithmetic expressions by first converting the given infixed expressions to postfixed expressions, and then evaluated the post fixed expression.
Repeat the exercise for this assignment (assignment 2) by using the data structure called Binary Trees. Your output must display the original expression, the postfixed expression representing the Binary tree, and the evaluated result.
Please bear in mind that 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.
PLEASE INCLUDE EVALUATE METHOD
previous assigment :
import java.util.*; class Arithmetic{ public String exp,postfixexp; public Arithmetic(String exp){ this.exp=exp; this.postfixexp=""; } //___________________________isBalance()__________________ public boolean isBalance(){ Stack<Integer> stk = new Stack<Integer>(); int i; for(i=0;i<exp.length();i++){ char ch=exp.charAt(i); if(ch=='('){ stk.push(i); } else if(ch==')'){ if(!stk.isEmpty()){ stk.pop(); } else{ return false; } } } if(stk.isEmpty()){ return true; } else{ return false; } } //__________________________postFixExpression()_______________ public int Prec(char ch) { switch (ch) { case '+': case '-': return 1; case '*': case '/': return 2; case '^': return 3; } return -1; } public void postFixExpression() { Stack<Character> stack = new Stack<>(); for (int i = 0; i<exp.length(); ++i) { char c = exp.charAt(i); if (Character.isLetterOrDigit(c)) postfixexp += c; else if (c == '(') stack.push(c); else if (c == ')') { while (!stack.isEmpty() && stack.peek() != '(') postfixexp += stack.pop(); stack.pop(); } else { while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek())){ postfixexp += stack.pop(); } stack.push(c); } } while (!stack.isEmpty()){ postfixexp += stack.pop(); } } public String getPostfix(){ return postfixexp; } //______________________evaluateRPN_____________________ public float evaluateRPN() { Stack<Float> stack=new Stack<>(); for(int i=0;i<postfixexp.length();i++) { char c=postfixexp.charAt(i); if(Character.isDigit(c)) stack.push((float)c - '0'); else { float val1 = stack.pop(); float val2 = stack.pop(); switch(c) { case '+': stack.push(val2+val1); break; case '-': stack.push(val2- val1); break; case '/': stack.push(val2/val1); break; case '*': stack.push(val2*val1); break; } } } return stack.pop(); } }
Algorithm
Let t be the expression tree
If t is not null then
If t.value is operand then
Return t.value
A= solve(t.left)
B= solve(t.right)
// calculate applies operator 't.value'
//on A and B, and returns value
Return calculate (A,B,t.value)
class Node{
char value;
Node left, right;
Node(char item){
value=item;
left=right=NULL;
}
}
class ExpressionTree{
//A utility function to check if 'c'
//is an operator
boolean is operator(char c){
if(c=='+'|| c =='-'
|| c =='*' || c =='/'
|| c=='^'){
return true;
}
return false;
}
//Utility function to do in order traversal
void inorder(Node t){
If(t != NULL){
inorder (t.left);
System. out.print(t.value+" ");
inorder (t.right);
}
}
//Returns root of constructed tree for given
// postfix expression
Node constructTree(char postfix []){
Stack<Node> St = new Stack<Node>();
Node t,t1,t2;
//if operand ,simply push into stack
if operand, simply push into stack
if (!isOperator(postfix[i]){
t= new Node (postfix[i]);
st.push(t);
}else // operator
{
t= s1.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;
}
public static void main (String args[]){
ExpressionTree et = new Expression Tree();
string postfix = "ab+EF*g*-";
char[] char array = postfix. toCharArray();
Node root = et.construct Tree(charArray);
System.out.println(" infix expression is")
et inorder(root);
}
}