EvaluateDeluxe.java

Below is the syntax highlighted version of EvaluateDeluxe.java from §1.3 Stacks and Queues.

/******************************************************************************
 *  Compilation:  javac EvaluateDeluxe.java
 *  Execution:    java EvaluateDeluxe
 *  Dependencies: Stack.java
 *
 *  Evaluates arithmetic expressions using Dijkstra's two-stack algorithm.
 *  Handles the following binary operators: +, -, *, / and parentheses.
 *
 *  % echo "3 + 5 * 6 - 7 * ( 8 + 5 )" | java EvaluateDeluxe
 *  -58.0
 *
 *
 *  Limitiations
 *  --------------
 *    -  can easily add additional operators and precedence orders, but they
 *       must be left associative (exponentiation is right associative)
 *    -  assumes whitespace between operators (including parentheses)
 *
 *  Remarks
 *  --------------
 *    -  can eliminate second phase if we enclose input expression
 *       in parentheses (and, then, could also remove the test
 *       for whether the operator stack is empty in the inner while loop)
 *    -  see http://introcs.cs.princeton.edu/java/11precedence/ for
 *       operator precedence in Java
 *
 ******************************************************************************/

import java.util.TreeMap;

public class EvaluateDeluxe {

    // result of applying binary operator op to two operands val1 and val2
    public static double eval(String op, double val1, double val2) {
        if (op.equals("+")) return val1 + val2;
        if (op.equals("-")) return val1 - val2;
        if (op.equals("/")) return val1 / val2;
        if (op.equals("*")) return val1 * val2;
        throw new RuntimeException("Invalid operator");
    }

    public static void main(String[] args) {

        // precedence order of operators
        TreeMap<String, Integer> precedence = new TreeMap<String, Integer>();
        precedence.put("(", 0);   // for convenience with algorithm
        precedence.put(")", 0);
        precedence.put("+", 1);   // + and - have lower precedence than * and /
        precedence.put("-", 1);
        precedence.put("*", 2);
        precedence.put("/", 2);

        Stack<String> ops  = new Stack<String>();
        Stack<Double> vals = new Stack<Double>();

        while (!StdIn.isEmpty()) {

            // read in next token (operator or value)
            String s = StdIn.readString();

            // token is a value
            if (!precedence.containsKey(s)) {
                vals.push(Double.parseDouble(s));
                continue;
            }

            // token is an operator
            while (true) {

                // the last condition ensures that the operator with higher precedence is evaluated first
                if (ops.isEmpty() || s.equals("(") || (precedence.get(s) > precedence.get(ops.peek()))) {
                    ops.push(s);
                    break;
                }

                // evaluate expression
                String op = ops.pop();

                // but ignore left parentheses
                if (op.equals("(")) {
                    assert s.equals(")");
                    break;
                }

                // evaluate operator and two operands and push result onto value stack
                else {
                    double val2 = vals.pop();
                    double val1 = vals.pop();
                    vals.push(eval(op, val1, val2));
                }
            }
        }

        // finished parsing string - evaluate operator and operands remaining on two stacks
        while (!ops.isEmpty()) {
            String op = ops.pop();
            double val2 = vals.pop();
            double val1 = vals.pop();
            vals.push(eval(op, val1, val2));
        }

        // last value on stack is value of expression
        StdOut.println(vals.pop());
        assert vals.isEmpty();
        assert ops.isEmpty();
    }
}