java - 用于表达式评估的 Dijkstra 双栈算法

Question

我正在阅读 book关于算法和数据结构，并尝试按照示例进行操作。我尝试实现的是 Dijkstra 的用于表达式评估的双堆栈算法。它以 ( 1 + 2 ) * 3 之类的字符串形式输入，然后计算表达式。我的代码可以编译，但没有产生正确的输出。

上述表达式的输出是:

3.0

这是我的代码:

public class Eval {
    public static void main(String[] args) {
        String s = "( 1 + 2 ) * 3";
        evaluateAndPrintResult(s);
    }
    public static void evaluateAndPrintResult(String s)
    {
        String[] str = s.split("\\s+");
        Queue<String> q = new LinkedList<String>();
        for(String ss : str)
            q.add(ss);
        Stack<String> ops = new Stack<String>();
        Stack<Double> vals = new Stack<Double>();
        while (!q.isEmpty())
        { // Read token, push if operator.
            String token = q.poll();
            if (token.equals("(")) ;
            else if (token.equals("+")) ops.push(s);
            else if (token.equals("-")) ops.push(s);
            else if (token.equals("*")) ops.push(s);
            else if (token.equals("/")) ops.push(s);
            else if (token.equals("sqrt")) ops.push(s);
            else if (token.equals(")"))
            { // Pop, evaluate, and push result if token is ")".
                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);
            } // Token not operator or paren: push double value.
            else vals.push(Double.parseDouble(token));
        }
        System.out.println(vals.pop());
    }
}   

我对程序的理解还不够深入，无法更正它。我怎样才能更正我的程序？

Answer 1

您的问题出在您使用ops.push(s) 的几个地方。您应该使用 ops.push(token)。

您正在推送整个表达式，您应该只推送当前 token 。

此代码正确打印 9.0。

public static void evaluateAndPrintResult(String s) {
    String[] str = s.split("\\s+");
    Queue<String> q = new LinkedList<>();
    q.addAll(Arrays.asList(str));
    Stack<String> ops = new Stack<>();
    Stack<Double> vals = new Stack<>();
    while (!q.isEmpty()) { // Read token, push if operator.
        String token = q.poll();
        if (token.equals("(")) {
        } else if (token.equals("+")) {
            ops.push(token);
        } else if (token.equals("-")) {
            ops.push(token);
        } else if (token.equals("*")) {
            ops.push(token);
        } else if (token.equals("/")) {
            ops.push(token);
        } else if (token.equals("sqrt")) {
            ops.push(token);
        } else if (token.equals(")")) { // Pop, evaluate, and push result if token is ")".
            // Replace the top exp with it' result.
            double v = vals.pop();
            String op = ops.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 {
            // Token not operator or paren: push double value.
            vals.push(Double.parseDouble(token));
        }
    }
    System.out.println(vals.pop());
}

public void test() {
    evaluateAndPrintResult("( ( 1 + 2 ) * 3 )");
}

但是，表达式 "( 1 + 2 ) * 3" 的计算结果仍为 3.0。要解决这个问题，您需要评估您推送的最后一个操作(如果有的话)。

public static void evaluateAndPrintResult(String s) {
    String[] str = s.split("\\s+");
    Queue<String> q = new LinkedList<>();
    q.addAll(Arrays.asList(str));
    Stack<String> ops = new Stack<>();
    Stack<Double> vals = new Stack<>();
    while (!q.isEmpty()) { // Read token, push if operator.
        String token = q.poll();
        if (token.equals("(")) {
        } else if (token.equals("+")) {
            ops.push(token);
        } else if (token.equals("-")) {
            ops.push(token);
        } else if (token.equals("*")) {
            ops.push(token);
        } else if (token.equals("/")) {
            ops.push(token);
        } else if (token.equals("sqrt")) {
            ops.push(token);
        } else if (token.equals(")")) {
            vals.push(evaluateOp(ops, vals));
        } else {
            // Token not operator or paren: push double value.
            vals.push(Double.parseDouble(token));
        }
    }
    System.out.println(evaluateOp(ops, vals));
}

private static Double evaluateOp(Stack<String> ops, Stack<Double> vals) {
    // Replace the top exp with its result.
    double v = vals.pop();
    String op = ops.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);
    }
    return v;
}

public void test() {
    evaluateAndPrintResult("( 1 + 2 ) * 3");
}

最后 - 一种更简洁的方法。

public static void evaluateAndPrintResult(String s) {
    String[] str = s.split("\\s+");
    Queue<String> q = new LinkedList<>();
    q.addAll(Arrays.asList(str));
    Stack<String> ops = new Stack<>();
    Stack<Double> vals = new Stack<>();
    while (!q.isEmpty()) { // Read token, push if operator.
        String token = q.poll();
        switch (token) {
            case "(":
                break;
            case "+":
            case "-":
            case "*":
            case "/":
            case "sqrt":
                ops.push(token);
                break;
            case ")":
                vals.push(evaluateOp(ops, vals));
                break;
            default:
                // Token not operator or paren: push double value.
                vals.push(Double.parseDouble(token));
                break;
        }
    }
    System.out.println(s + " = " + evaluateOp(ops, vals));
}

private static Double evaluateOp(Stack<String> ops, Stack<Double> vals) {
    // Replace the top exp with its result.
    double v = vals.pop();
    if (!ops.empty()) {
        String op = ops.pop();
        switch (op) {
            case "+":
                v = vals.pop() + v;
                break;
            case "-":
                v = vals.pop() - v;
                break;
            case "*":
                v = vals.pop() * v;
                break;
            case "/":
                v = vals.pop() / v;
                break;
            case "sqrt":
                v = Math.sqrt(v);
                break;
            default:
                break;
        }
    }
    return v;
}

public void test() {
    evaluateAndPrintResult("( ( 1 + 2 ) * 3 )");
}