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}