1 /******************************************************************************  2  *  Compilation:  javac EvaluateDeluxe.java  3  *  Execution:    java EvaluateDeluxe  4  *  Dependencies: Stack.java  5  *  6  *  Evaluates arithmetic expressions using Dijkstra's two-stack algorithm.  7  *  Handles the following binary operators: +, -, *, / and parentheses.  8  *  9  *  % echo "3 + 5 * 6 - 7 * ( 8 + 5 )" | java EvaluateDeluxe 10  *  -58.0 11  * 12  * 13  *  Limitiations 14  *  -------------- 15  *    -  can easily add additional operators and precedence orders, but they 16  *       must be left associative (exponentiation is right associative) 17  *    -  assumes whitespace between operators (including parentheses) 18  * 19  *  Remarks 20  *  -------------- 21  *    -  can eliminate second phase if we enclose input expression 22  *       in parentheses (and, then, could also remove the test 23  *       for whether the operator stack is empty in the inner while loop) 24  *    -  see http://introcs.cs.princeton.edu/java/11precedence/ for 25  *       operator precedence in Java 26  * 27  ******************************************************************************/ 28  29 import java.util.TreeMap; 30  31 public class EvaluateDeluxe { 32  33     // result of applying binary operator op to two operands val1 and val2 34     public static double eval(String op, double val1, double val2) { 35         if (op.equals("+")) return val1 + val2; 36         if (op.equals("-")) return val1 - val2; 37         if (op.equals("/")) return val1 / val2; 38         if (op.equals("*")) return val1 * val2; 39         throw new RuntimeException("Invalid operator"); 40     } 41  42     public static void main(String[] args) { 43  44         // precedence order of operators 45         TreeMap
     
       precedence = new TreeMap
      
       (); 46         precedence.put("(", 0);   // for convenience with algorithm 47         precedence.put(")", 0);   48         precedence.put("+", 1);   // + and - have lower precedence than * and / 49         precedence.put("-", 1); 50         precedence.put("*", 2); 51         precedence.put("/", 2); 52  53         Stack
       
         ops  = new Stack
        
         (); 54         Stack
         
           vals = new Stack
          
           (); 55 56 while (!StdIn.isEmpty()) { 57 58 // read in next token (operator or value) 59 String s = StdIn.readString(); 60 61 // token is a value 62 if (!precedence.containsKey(s)) { 63 vals.push(Double.parseDouble(s)); 64 continue; 65 } 66 67 // token is an operator 68 while (true) { 69 70 // the last condition ensures that the operator with higher precedence is evaluated first 71 if (ops.isEmpty() || s.equals("(") || (precedence.get(s) > precedence.get(ops.peek()))) { 72 ops.push(s); 73 break; 74 } 75 76 // evaluate expression 77 String op = ops.pop(); 78 79 // but ignore left parentheses 80 if (op.equals("(")) { 81 assert s.equals(")"); 82 break; 83 } 84 85 // evaluate operator and two operands and push result onto value stack 86 else { 87 double val2 = vals.pop(); 88 double val1 = vals.pop(); 89 vals.push(eval(op, val1, val2)); 90 } 91 } 92 } 93 94 // finished parsing string - evaluate operator and operands remaining on two stacks 95 while (!ops.isEmpty()) { 96 String op = ops.pop(); 97 double val2 = vals.pop(); 98 double val1 = vals.pop(); 99 vals.push(eval(op, val1, val2));100 }101 102 // last value on stack is value of expression103 StdOut.println(vals.pop());104 assert vals.isEmpty();105 assert ops.isEmpty();106 }107 }