001package algs13; 002import stdlib.*; 003import java.util.TreeMap; 004/* *********************************************************************** 005 * Compilation: javac EvaluateDeluxe.java 006 * Execution: java EvaluateDeluxe 007 * Dependencies: Stack.java 008 * 009 * Evaluates arithmetic expressions using Dijkstra's two-stack algorithm. 010 * Handles the following binary operators: +, -, *, / and parentheses. 011 * 012 * % echo "3 + 5 * 6 - 7 * ( 8 + 5 )" | java EvaluateDeluxe 013 * -58.0 014 * 015 * 016 * Limitiations 017 * -------------- 018 * - can easily add additional operators and precedence orders, but they 019 * must be left associative (exponentiation is right associative) 020 * - assumes whitespace between operators (including parentheses) 021 * 022 * Remarks 023 * -------------- 024 * - can eliminate second phase if we enclose input expression 025 * in parentheses (and, then, could also remove the test 026 * for whether the operator stack is empty in the inner while loop) 027 * - see http://introcs.cs.princeton.edu/java/11precedence/ for 028 * operator precedence in Java 029 * 030 *************************************************************************/ 031 032public class XEvaluateDeluxe { 033 034 // result of applying binary operator op to two operands val1 and val2 035 public static double eval(String op, double val1, double val2) { 036 if (op.equals("+")) return val1 + val2; 037 if (op.equals("-")) return val1 - val2; 038 if (op.equals("/")) return val1 / val2; 039 if (op.equals("*")) return val1 * val2; 040 throw new Error("Invalid operator"); 041 } 042 043 public static void main(String[] args) { 044 045 StdIn.fromString ("1 + 2 + 3"); 046 047 // precedence order of operators 048 TreeMap<String, Integer> precedence = new TreeMap<>(); 049 precedence.put("(", 0); // for convenience with algorithm 050 precedence.put(")", 0); 051 precedence.put("+", 1); // + and - have lower precedence than * and / 052 precedence.put("-", 1); 053 precedence.put("*", 2); 054 precedence.put("/", 2); 055 056 Stack<String> ops = new Stack<>(); 057 Stack<Double> vals = new Stack<>(); 058 059 while (!StdIn.isEmpty()) { 060 061 // read in next token (operator or value) 062 String s = StdIn.readString(); 063 064 // token is a value 065 if (!precedence.containsKey(s)) { 066 vals.push(Double.parseDouble(s)); 067 continue; 068 } 069 070 // token is an operator 071 while (true) { 072 073 // the last condition ensures that the operator with higher precedence is evaluated first 074 if (ops.isEmpty() || s.equals("(") || (precedence.get(s) > precedence.get(ops.peek()))) { 075 ops.push(s); 076 break; 077 } 078 079 // evaluate expression 080 String op = ops.pop(); 081 082 // but ignore left parentheses 083 if (op.equals("(")) { 084 if (!s.equals(")")) throw new Error (); 085 break; 086 } 087 088 // evaluate operator and two operands and push result onto value stack 089 else { 090 double val2 = vals.pop(); 091 double val1 = vals.pop(); 092 vals.push(eval(op, val1, val2)); 093 } 094 } 095 } 096 097 // finished parsing string - evaluate operator and operands remaining on two stacks 098 while (!ops.isEmpty()) { 099 String op = ops.pop(); 100 double val2 = vals.pop(); 101 double val1 = vals.pop(); 102 vals.push(eval(op, val1, val2)); 103 } 104 105 // last value on stack is value of expression 106 StdOut.println(vals.pop()); 107 if (!vals.isEmpty()) throw new Error (); 108 if (!ops.isEmpty()) throw new Error (); 109 } 110}