algs4 1.3.9 一道直击 双栈算法 精髓的练习题

AutoCompleteParentheses.java

package life.yanfeng.study.algorithm;

import edu.princeton.cs.algs4.StdOut;

// for 1.3.9
public class AutoCompleteParentheses {
    /// from 1.3.1.7 Dijkstra 的双栈表达式求值算法
    static double evaluate(String exp) {
        Stack<String> ops = new Stack<>();
        Stack<Double> vals = new Stack<>();

        for (String s : exp.split(" ")) {
            // 读取字符串, 如果是运算符则压入栈.
            if (s.equals("(")) {
                continue;
            } else if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("sqrt")) {
                ops.push(s);
            } else if(s.equals(")")) {
                // 如果字符维 ")", 则弹出运算符和操作数, 计算结果,并将结果压入栈.
                String op = ops.pop();
                double v = vals.pop();
                if (op.equals("+")) v = vals.pop() + v;
                else if (op.equals("-")) v = vals.pop() - v;
                else if (op.equals("*")) v = vals.pop() * v;
                else if (op.equals("/")) v = vals.pop() / v;
                else if (op.equals("sqrt")) v = Math.sqrt(v);
                vals.push(v);
            } else { // 如果既不是运算符,也不是括号, 则将它作为 double 值压入栈.
                vals.push(Double.parseDouble(s));
            }
        }

        return vals.pop();
    }

    /// 自动补全 左括号 . 反向推导表达式的原始形式.
    /// 核心思路, 也即: 双栈表达式的精髓在于: 使用同一个栈, 同时存储 操作数 和 中间运算结果.
    static String completeParentheses(String exp) {
        Stack<String> ops = new Stack<>();
        Stack<String> vals = new Stack<>();

        for (String s : exp.split(" ")) {
            // 读取字符串, 如果是运算符则压入栈.
            if (s.equals("(")) {
                continue;
            } else if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("sqrt")) {
                ops.push(s);
            } else if(s.equals(")")) {
                // 如果字符维 ")", 则弹出运算符和操作数, 计算结果,并将结果压入栈.
                String op = ops.pop();
                String v = vals.pop();
                if (op.equals("+") || op.equals("-") || op.equals("*") || op.equals("/"))
                    v = String.format("( %s %s %s )", vals.pop(), op, v);
                else if (op.equals("sqrt"))
                    v = String.format("( %s %s )", vals.pop(), op, v);
                vals.push(v);
            } else { // 如果既不是运算符,也不是括号, 则将它作为 值压入栈.
                vals.push(s);
            }
        }

        return vals.pop();
    }

    public static void main(String[] args) {
        /*
        1.3.1.7, 算术表达式的求职, 竟然是 直接忽略左括号的.
        1.3.1.7 没有使用 "优先级", 而是用 括号来表达所有的运算顺序.
        */

        String exp = "1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )";
        String fullExp = completeParentheses(exp);
        StdOut.println(fullExp);

        StdOut.println(evaluate(fullExp) == evaluate(exp));
    }
}

核心思路, 在于: 使用同一个栈, 同时存储 操作数 和 中间运算结果. 核心思路, 这可能也是 双栈表达式的 的精髓所在.

网上有一些 很尬的 演算法. ...

不过, 我还是找到了 类似思路的 博主: https://www.programmerall.com/article/1029117890/