package com.matao.fundamentals;

/**
 * Created by matao on 5/27/16.
 * Dijkstra 双栈算数表达式求值算法
 * 1) 将操作数压入操作数栈
 * 2) 将运算符压入运算符栈
 * 3) 忽略左括号
 * 4) 遇到右括号时,弹出一个操作符,弹出所需数量的操作数,二元运算后弹出的操作数在前
 * 并将运算符和操作数的运算结果压入操作数栈
 */
public class Evaluate {

    public static double evaluate(String exp) {
        Stack<String> operators = new Stack<>();
        Stack<Double> values = new Stack<>();
        for (String s : exp.split(" ")) {
            switch (s) {
                case "(":
                    break;
                case "+":
                case "-":
                case "*":
                case "/":
                case "sqrt":
                    operators.push(s);
                    break;
                case ")":
                    String operator = operators.pop();
                    double value = values.pop();
                    switch (operator) {
                        case "+":
                            values.push(values.pop() + value);
                            break;
                        case "-":
                            values.push(values.pop() - value);
                            break;
                        case "*":
                            values.push(values.pop() * value);
                            break;
                        case "/":
                            values.push(values.pop() / value);
                            break;
                        case "sqrt":
                            values.push(Math.sqrt(value));
                            break;
                        default:
                            break;
                    }
                    break;
                default:    // number
                    values.push(Double.parseDouble(s));
                    break;
            }
        }
        return values.pop();
    }


    public static void main(String[] args) {
        String exp1 = "( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )";     // expected 101.0
        System.out.println(evaluate(exp1));

        String exp2 = "( ( 1 + sqrt ( 5.0 ) ) / 2.0 )";     // expected 101
        System.out.println(evaluate(exp2));

    }
}

@@ -62,16 +62,23 @@
 /27/16.%0A
+ * %3Cp%3E%0A
  * Dijks
@@ -84,136 +84,369 @@
 stra
- %E5%8F%8C%E6%A0%88%E7%AE%97%E6%95%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC%E7%AE%97%E6%B3%95%0A * 1) %E5%B0%86%E6%93%8D%E4%BD%9C%E6%95%B0%E5%8E%8B%E5%85%A5%E6%93%8D%E4%BD%9C%E6%95%B0%E6%A0%88%0A * 2) %E5%B0%86%E8%BF%90%E7%AE%97%E7%AC%A6%E5%8E%8B%E5%85%A5%E8%BF%90%E7%AE%97%E7%AC%A6%E6%A0%88%0A * 3) %E5%BF%BD%E7%95%A5%E5%B7%A6%E6%8B%AC%E5%8F%B7%0A * 4) %E9%81%87%E5%88%B0%E5%8F%B3%E6%8B%AC%E5%8F%B7%E6%97%B6,%E5%BC%B9%E5%87%BA%E4%B8%80%E4%B8%AA%E6%93%8D%E4%BD%9C%E7%AC%A6,%E5%BC%B9%E5%87%BA%E6%89%80%E9%9C%80%E6%95%B0%E9%87%8F%E7%9A%84%E6%93%8D%E4%BD%9C%E6%95%B0,%E4%BA%8C%E5%85%83%E8%BF%90%E7%AE%97%E5%90%8E%E5%BC%B9%E5%87%BA%E7%9A%84%E6%93%8D%E4%BD%9C%E6%95%B0%E5%9C%A8%E5%89%8D%0A * %E5%B9%B6%E5%B0%86%E8%BF%90%E7%AE%97%E7%AC%A6%E5%92%8C%E6%93%8D%E4%BD%9C%E6%95%B0%E7%9A%84%E8%BF%90%E7%AE%97%E7%BB%93%E6%9E%9C%E5%8E%8B%E5%85%A5%E6%93%8D%E4%BD%9C%E6%95%B0%E6%A0%88
+%E2%80%99s Two-Stack Algorithm for Expression Evaluation%0A * 1) Push operands onto the operand stack.%0A * 2) Push operators onto the operator stack.%0A * 3) Ignore left parentheses.%0A * 4) On encountering a right parenthesis, pop an operator, pop the requisite number of operands,%0A *    and push onto the operand stack the result of applying that operator to those operands.
 %0A */

revise comments