Write a recursive MARS program that can compute the value of an expression in pa

Question

Write a recursive MARS program that can compute the value of an expression in parentheses. The program should accept an input string, sequentially examine each character, invoke the procedure calc_expr every time it sees a new open parenthesis, return from that procedure when the parenthesis is closed, and print the answer when the outermost parenthesis is closed. We will only test with valid inputs including decimal integers, spaces, and +, -, *, / operators. The program runs until the user enters a string starting with "e". Within parentheses, the expression is evaluated from left to right, i.e., (6/2+7/5) does 6/2 (which is 3), 3+7 (which is 10), 10/5 (which is 2). Here's an example run of the program:
Enter the expression you want evaluated:
((4+3)-((27/9)*2))
The answer is: 1
Enter the expression you want evaluated:
(1*(2 * (3 * (4 * 5))))
The answer is: 120
Enter the expression you want evaluated:
exit

Explanation / Answer

ExpressionEvaluation.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class ExpressionEvaluation {

   private BufferedReader br;
   private String expression;
   private Stack<Integer> values;
   private char[] tokens;
   private Stack<Character> opertors;
  
   public ExpressionEvaluation() {
       // TODO Auto-generated constructor stub
   }

   public void takeInput() throws IOException{
       br = new BufferedReader(new InputStreamReader(System.in));
       expression = br.readLine();
   }
  
   public int evaluate(){
      
       values = new Stack<Integer>();
       tokens = expression.toCharArray();
       opertors = new Stack<Character>();

       /*for (int i = 0; i < tokens.length; i++){
           System.out.print(tokens[i]+":");
       }*/
      
for (int i = 0; i < tokens.length; i++){
// If it is space
if (tokens[i] == ' ')
continue;

// If number push it into the stack
if (tokens[i] >= '0' && tokens[i] <= '9')
{
StringBuffer sbuffer = new StringBuffer();
// Taking full number that is all digits
int temp=0;
while (i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9'){
sbuffer.append(tokens[i]);
        if(i < tokens.length && tokens[i+1] >= '0' && tokens[i+1] <= '9'){
            i++;
        }
        else{
            break;
        }
}
values.push(Integer.parseInt(sbuffer.toString()));
}

else if (tokens[i] == '('){
   opertors.push(tokens[i]);
}
else if (tokens[i] == ')'){
while (opertors.peek() != '(')
values.push(cal_expr(opertors.pop(), values.pop(), values.pop()));
opertors.pop();
}

// if it is an operator.
else if (tokens[i] == '-' || tokens[i] == '+' || tokens[i] == '/' || tokens[i] == '*')
{
while (!opertors.empty() && checkPrecedence(tokens[i], opertors.peek())){
values.push(cal_expr(opertors.pop(), values.pop(), values.pop()));
}
opertors.push(tokens[i]);
}
/* System.out.println("values: "+values);
System.out.println("ops: "+opertors);*/
}

while (!opertors.empty()){
   /*System.out.println("opspeek :"+opertors.peek());
   System.out.println("values peek :"+values.peek());
   System.out.println("values:"+values);*/
values.push(cal_expr(opertors.pop(), values.pop(), values.pop()));
}
return values.pop();
}

public static boolean checkPrecedence(char operator1, char operator2){
//System.out.println("operator1:"+operator1+" operator2: "+operator2);
if (operator2 == '(' || operator2 == ')')
return false;
if ((operator1 == '*' || operator1 == '/') && (operator2 == '+' || operator2 == '-'))
return false;
else
return true;
}

//Calculating the value
public static int cal_expr(char op, int b, int a)
{
switch (op){
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
if (b == 0)
throw new
UnsupportedOperationException("Cannot divide by zero");
return a / b;
}
return 0;
}
   public static void main(String[] args) throws IOException {

       ExpressionEvaluation ee = new ExpressionEvaluation();
       ee.takeInput();
       System.out.println(ee.evaluate());

   }

}

Output:

((4+3)-((27/9)*2))
1

(1*(2 * (3 * (4 * 5))))
120

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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