Question

In: Computer Science

In assignment 1 you had used the data structure called Stack to evaluate arithmetic expressions by...

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();     
    } 
    
}

Solutions

Expert Solution

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);

}

}


Related Solutions

In assignment 1 you had used the data structure called Stack to evaluate arithmetic expressions by...
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...
Assignment #2 (JAVA) In assignment 1 you had used the data structure called Stack to evaluate...
Assignment #2 (JAVA) 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...
1. Implement the stack abstract data type. Write it as a separate class called Stack. For...
1. Implement the stack abstract data type. Write it as a separate class called Stack. For simplicity the data type to be stored in the stack is String but you can also use generic type. 2. Test your class implementation by calling push() and pop(). If the stack is empty (size equals zero) pop() should return null and print that “stack is empty”. If stack is full (size equals max) push() returns false and prints that “stack is full”. This...
C++ OOP Make a program to evaluate infix arithmetic expressions containing integer operands and the operators...
C++ OOP Make a program to evaluate infix arithmetic expressions containing integer operands and the operators + (addition), - (subtraction), * (multiplication), / (division) and pairs of parentheses, properly nested. Use the following two-stack algorithm (by E. W. Dijkstra): If the next token in the expression is an integer, push the integer onto the value stack. If the next token in the expression is an operator, If the operator stack is empty or the priority of the operator is greater...
Discuss the stack data structure. What is it? How can it be used? What support exists...
Discuss the stack data structure. What is it? How can it be used? What support exists for stacks in the Java Class Library Collections Framework? Do you think this support is easy to understand and use? Why or why not? Discuss the pros and cons of creating your own stack classes vs. using those provided by the Java Class Library Collections Framework. Make sure you take into consideration the ability to handle any kind of objects (generics).
This laboratory assignment involves implementing a data structure called a map. A map associates objects called...
This laboratory assignment involves implementing a data structure called a map. A map associates objects called keys with other objects called values. It is implemented as a Java class that uses arrays internally. 1. Theory. A map is a set of key-value pairs. Each key is said to be associated with its corresponding value, so there is at most one pair in the set with a given key. You can perform the following operations on maps. You can test if...
In this assignment, we will explore some simple expressions and evaluate them. We will use an...
In this assignment, we will explore some simple expressions and evaluate them. We will use an unconventional approach and severely limit the expressions. The focus will be on operator precedence. The only operators we support are logical or (|), logical and (&), less than (<), equal to (=), greater than (>), add (+), subtract (-), multiply (*) and divide (/). Each has a precedence level from 1 to 5 where higher precedence operators are evaluated first, from left-to-right. For example,...
C++ Data Structure Write a program to change following infix expressions to postfix expressions using a...
C++ Data Structure Write a program to change following infix expressions to postfix expressions using a stack a) D-B+C b) C*D+A*B c) (A*B)*C+D*F-C d) (A-4*(B-C)-D/E)*F
0. Introduction. This laboratory assignment involves implementing a data structure called a map. A map associates...
0. Introduction. This laboratory assignment involves implementing a data structure called a map. A map associates objects called keys with other objects called values. It is implemented as a Java class that uses arrays internally. 1. Theory. A map is a set of key-value pairs. Each key is said to be associated with its corresponding value, so there is at most one pair in the set with a given key. You can perform the following operations on maps. You can...
In this assignment you are to utilize the Node data structure provided on Blackboard. In this...
In this assignment you are to utilize the Node data structure provided on Blackboard. In this assignment you are to write a main program that implements two methods and a main method as their driver. So, only main and two methods with it. Implementation Details: Method 1: ^^^^^^^^^ Parameters and return type: Takes as parameters an array of integers, the size of the array of integer (.length is acceptable also) and it should return a Node that is supposed to...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT