Problem: (what I have so far is on the bottom, right track...?) Implementing Exp

Question

Problem: (what I have so far is on the bottom, right track...?)

Implementing Expression Trees:

Implement a class called ExpressionTree . The constructor to ExpressionTree will take in a String that contains a postfix expression. The operands will be integers and the binary operators will be restricted to +, -, *, and divide. Individual tokens, that is the operands and operators, will be delimited by spaces. So for example:

34 2 - 5 *

would mean (34-2)*5.

Your constructor will run the stack based algorithm we discussed in class to build an expression tree. ExpressionNodes will be a nested class within ExpressionTree. You may use any code posted on canvas or from the Weiss textbook as a starting point for this class.

Once you have the ExpressionTree constructed you should provide the following four methods:

public int eval() - this method, when invoked on an expression tree object will return the integer value associated with evaluating the expression tree. It will need to call a private recursive method that takes in the root.

public String postfix() - this method, when invoked on an expression tree object will return a String that contains the corresponding postfix expression. It will need to call a private recursive method that takes in the root.

public String prefix() - this method, when invoked on an expression tree object will return a String that contains the corresponding prefix expression. It will need to call a private recursive method that takes in the root.

public String infix() - this method, when invoked on an expression tree object will return a String that contains the corresponding correct infix expression. Keep in mind that parenthesis will be needed (excessive parenthesis will be tolerated as long as it is correct). It will need to call a private recursive method that takes in the root.

Write a class called Problem1.java that instantiates an expression, and demonstrate your methods.

import java.util.Scanner;

public class ExpressionTree {

   /*
   * public char operator;
   *
   * public boolean isNumber;
   *
   *
   */

   int value;
  
   String operator;
   int operand1;
   int operand2;

   int result = 0;
  
   private ExpressionNode root;

   public ExpressionTree(String expression) {
       MyStack stack = new MyStack();

       Scanner token = new Scanner(expression);

       while (token.hasNext()) {
           if (token.hasNext()) {
               // Process operand
               value = token.nextInt();
               if (stack.isFull()) {
                   System.out.println("Too many operands- stack overflow");
               }
               stack.push(value);
           } else {
               // process operator
               operator = token.next();

               // obtain second operand from stack
               if (stack.isEmpty()) {
                   System.out.println("Not enough operands - stack " + "underflow");
               }

               operand2 = stack.top();
               stack.pop();

               // Obtain first operand from stack
               if (stack.isEmpty()) {
                   System.out.println("Not enough operands - stack " + "underflow");
               }

               operand1 = stack.top();
               stack.pop();

               // Perform operation
               if (operator.equals("/")) {
                   result = operand1 / operand2;
               } else if (operator.equals("*")) {
                   result = operand1 * operand2;
               } else if (operator.equals("+")) {
                   result = operand1 + operand2;
               } else if (operator.equals("-")) {
                   result = operand1 - operand2;
               } else {
                   System.out.println("Illegal symbol:" + operator);
               }

               // push result of operation onto stack
               stack.push(result);
           }
       }

       // obtain final result from stack
       if (stack.isEmpty()) {
           System.out.println("Not enough operands - stack underflow");
       }
       result = stack.top();
       stack.pop();
       if (!stack.isEmpty()) {
           System.out.println("Too many operands - operands left over");
       }

       System.out.println(result);
   }

   public static class ExpressionNode {
       public ExpressionNode operand1;
       public ExpressionNode operand2;
       public ExpressionNode operator;

       public ExpressionNode(ExpressionNode int operand1, ExpressionNode String operator, ExpressionNode int operand2) {
   this.operand1 = left;
   this.operator = operator;
   this.operand2 = right;
   }
   }

   public String toString() {
       StringBuilder sb = new StringBuilder();

       return sb.toString();
   }

   public int eval() {

   }

   public String postfix() {
      
      

   }

   public String prefix() {
       if(node.left != null){
           prefix(node.left);
       }
       if(node.right != null){
           prefix(node.right);
       }

   }

   public String infix() {

   }

}

My helper class:

import java.util.LinkedList;

public class MyStack<T> {
  
   private LinkedList<T> stack;

   public MyStack(){
       stack = new LinkedList<T>();
   }
  
   int topIndex = -1;
  
   // if stack is empty return null, else remove element from stack
   public T pop(){

       if(stack.size() == 0){
           return null;
       }
       else{
           return stack.remove();
       }
   }

   // displays first elements in stack
   public T peek(){
       return stack.getFirst();
   }

   // adds element to the top of stack
   public void push(T e){
       stack.addFirst(e);
   }
  
  
// only used for TwoStackQueue
public boolean isEmpty(){
if (topIndex == -1)
   return true;
else
   return false;
}
  
public boolean isFull(){
   if (topIndex ==(stack.size() -1)){
       return true;
   }else
       return false;
}

   public T top() {
       T topOfStack = null;
       if (!isEmpty()){
           topOfStack= stack.get(stack.size() - 1);
       }else{
           System.out.println("Top attempted on an empty" + "stack");
       }
       return topOfStack;
   }

}

Explanation / Answer

Expected Output:

Expression Tree

Enter equation in postfix form

+-+7*/935/82*/625

Prefix : +-+7*/935/82*/625

Infix : 7+9/3*5-8/2+6/2*5

Postfix : 793/5*+82/-62/5*+

Evaluated Result : 33.0

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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