Write a recursive method, eval, to evaluate a postfix expression. The expression

Question

Write a recursive method, eval, to evaluate a postfix expression. The expression is represented as a String and contains the following operators: +, -, * and /. For simplicity, assume that all the numbers are single digit and unsigned, for instance 5, or 6 but not 23, 124 or -4. An example of an input is: ”873-*4+23- *58-+”.

Programming hint: in order to transform a single character located at posi- tion i in a string exp to its numerical value, you may use:

val = Character.getNumericValue(exp.charAt(i));

class MyInt { public int val; }

public class Postfix {

// Public recursive method. public static double recEval(String exp, MyInt i) { }

2 // Public non-recursive public static double eval(String exp) {

MyInt i = new MyInt(); i.val = exp.length() - 1; return recEval(exp, i); }

Explanation / Answer

import java.util.*;

public class Postfix {
public static void main(String[] args) {
System.out.println(postfixEvaluate("1 2 +")); // 3
System.out.println(postfixEvaluate("1 2 3 * + 4 +")); // 11
System.out.println(postfixEvaluate("5 2 4 * + 7 -")); // 6
System.out.println(postfixEvaluate("2 3 + 4 5 * +")); // 25
System.out.println(postfixEvaluate("8 5 * 7 4 2 + * +")); // 82
System.out.println(postfixEvaluate("6 8 2 / 1 - *")); // 18
}
  
// Evaluates the given postfix expression string and returns the result.
// Precondition: expression consists only of integers, +-*/, and spaces in
// proper postfix format such as "2 3 - 4 *"
public static int postfixEvaluate(String exp) {
      Stack<Integer> s = new Stack<Integer> ();
       Scanner tokens = new Scanner(exp);
      
       while (tokens.hasNext()) {
           if (tokens.hasNextInt()) {
               s.push(tokens.nextInt());
           } else {
               int num2 = s.pop();
               int num1 = s.pop();
               String op = tokens.next();
              
               if (op.equals("+")) {
                   s.push(num1 + num2);
               } else if (op.equals("-")) {
                   s.push(num1 - num2);
               } else if (op.equals("*")) {
                   s.push(num1 * num2);
               } else {
                   s.push(num1 / num2);
               }
              
           // "+", "-", "*", "/"
           }
       }
       return s.pop();
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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