java - 如何修复此表达式计算器中的错误？

Question

我在 stackoverflow 上找到了一个表达式计算器:https://stackoverflow.com/a/26227947/8305657

我对其进行了修改并添加了额外的功能来满足我的需求。这是我的代码:

public static double compute(final String str) {
    return new Object() {
    int pos = -1, ch;
        void nextChar() {
            ch = (++pos < str.length()) ? str.charAt(pos) : -1;
        }
        boolean eat(int charToEat) {
            while(ch == ' ') {
                nextChar();
            }
            if(ch == charToEat) {
                nextChar();
                return true;
            }
            return false;
        }
        double parse() {
            nextChar();
            double x = parseExpression();
            if(pos < str.length()) {
                throw new RuntimeException("Unexpected: " + (char) ch);
            }
            return x;
        }
        // Grammar:
        // expression = term | expression `+` term | expression `-` term
        // term = factor | term `*` factor | term `/` factor
        // factor = `+` factor | `-` factor | `(` expression `)`
        //        | number | functionName factor | factor `^` factor
        double parseExpression() {
            double x = parseTerm();
            for(;;) {
                if(eat('+')) { //addition
                    x += parseTerm();
                }
                else if(eat('-')) { //subtraction
                    x -= parseTerm();
                }
                else {
                    return x;
                }
            }
        }
        double parseTerm() {
            double x = parseFactor();
            for(;;) {
                if(eat('×')) { //multiplication
                    x *= parseFactor();
                }
                else if(eat('÷')) { //division
                    x /= parseFactor();
                }
                else {
                    return x;
                }
            }
        }
        double parseFactor() {
            if(eat('+')) { //unary plus
                return parseFactor(); //unary plus
            }
            if(eat('-')) { //unary minus
                return -parseFactor();
            }
            double x;
            int startPos = this.pos;
            if(eat('(')) { //parentheses
                x = parseExpression();
                eat(')');
            }
            else if((ch >= '0' && ch <= '9') || ch == '.') { //numbers
                while((ch >= '0' && ch <= '9') || ch == '.') {
                    nextChar();
                }
                x = Double.parseDouble(str.substring(startPos, this.pos));
            }
            else if(ch >= 'a' && ch <= 'z' || ch == '!') { //functions
                while(ch >= 'a' && ch <= 'z' || ch == '!') {
                    nextChar();
                }
                String func = str.substring(startPos, this.pos);
                x = parseFactor();
                if(func.equals("sqrt")) {
                    x = Math.sqrt(x);
                }
                else if(func.equals("log")) {
                    x = Math.log10(x);
                }
                else if(func.equals("ln")) {
                    x = Math.log(x);
                }
                else if(func.equals("sin")) {
                    x = Math.sin(Math.toRadians(x));
                }
                else if(func.equals("cos")) {
                    x = Math.cos(Math.toRadians(x));
                }
                else if(func.equals("tan")) {
                    x = Math.tan(Math.toRadians(x));
                }
                else if(func.equals("sinh")) {
                    x = Math.sinh(x);
                }
                else if(func.equals("cosh")) {
                    x = Math.cosh(x);
                }
                else if(func.equals("tanh")) {
                    x = Math.tanh(x);
                }
                else if(func.equals("!")) {
                    int fact = 1;
                    double number = x;
                    for(int i = 1; i <= number; i++) {
                        fact *= i;
                    }
                    x = fact;
                }
                else {
                    throw new RuntimeException("Unknown function: " + func);
                }
            }
            else {
                throw new RuntimeException("Unexpected: " + (char) ch);
            }
            if(eat('^')) { //exponentiation
                x = Math.pow(x, parseFactor());
            }
            return x;
        }
    }.parse();
}

这个表达式求值器中的错误似乎与求幂有关。例如，如果我向求值器提供字符串 "sin(sqrt(5))^2"，它会返回答案 0.08715574274765818(以弧度为单位)，这是不正确的。正确答案是0.618974196(以弧度为单位)。我发现它给出错误答案的原因是，当涉及到求幂和内置函数时，它的运算顺序是错误的。它实际上将表达式计算为 sin(sqrt(5)^2)，而不是像预期那样将表达式计算为 sin(sqrt(5))^2。正如您所看到的，它不是在最后进行求幂，而是在中间进行。这个问题在所有功能中都存在。如果我同时使用任何两个函数并在最后求幂，例如 log(ln(8))^2 它仍然会出错。

这个问题甚至在我对原始评估器进行任何操作之前就已经存在，因为我测试了具有相同问题的原始代码。我被这个问题困扰了一段时间，不知道如何修复这个错误。如果有人对此进行了错误修复，我将不胜感激。

Answer 1

在我看来，问题是 parseFactor 的最后一行总是检查 ^ 运算符。所以 (5)^2 被认为是一个 parseFactor 表达式，因此 sin(5)^2 == sin 25 。我认为你可以通过改变语法来解决这个问题，如下所示:

Grammar:
expression = term | expression `+` term | expression `-` term
term = pow | term `*` pow | term `/` pow
pow = factor | pow ^ factor
factor = `+` pow  | `-` pow | `(` expression `)`
        | number | functionName factor

代码:

 public static double compute(final String str) {
        return new Object() {
            int pos = -1, ch;

            void nextChar() {
                ch = (++pos < str.length()) ? str.charAt(pos) : -1;
            }

            boolean eat(int charToEat) {
                while (ch == ' ') {
                    nextChar();
                }
                if (ch == charToEat) {
                    nextChar();
                    return true;
                }
                return false;
            }

            double parse() {
                nextChar();
                double x = parseExpression();
                if (pos < str.length()) {
                    throw new RuntimeException("Unexpected: " + (char) ch);
                }
                return x;
            }

            double parseExpression() {
                double x = parseTerm();
                for (; ; ) {
                    if (eat('+')) { //addition
                        x += parseTerm();
                    } else if (eat('-')) { //subtraction
                        x -= parseTerm();
                    } else {
                        return x;
                    }
                }
            }

            double parseTerm() {
                double x = parsePow();
                for (; ; ) {
                    if (eat('×')) { //multiplication
                        x *= parsePow();
                    } else if (eat('÷')) { //division
                        x /= parsePow();
                    } else {
                        return x;
                    }
                }
            }

            double parsePow() {
                double x = parseFactor();
                for (; ; ) {
                    if (eat('^')) {
                        x = Math.pow(x, parseFactor());
                    } else {
                        return x;
                    }
                }
            }


            double parseFactor() {
                if (eat('+')) { //unary plus
                    return parsePow(); //unary plus
                }
                if (eat('-')) { //unary minus
                    return -parsePow();
                }
                double x;
                int startPos = this.pos;
                if (eat('(')) { //parentheses
                    x = parseExpression();
                    eat(')');
                } else if ((ch >= '0' && ch <= '9') || ch == '.') { //numbers
                    while ((ch >= '0' && ch <= '9') || ch == '.') {
                        nextChar();
                    }
                    x = Double.parseDouble(str.substring(startPos, this.pos));
                } else if (ch >= 'a' && ch <= 'z' || ch == '!') { //functions
                    while (ch >= 'a' && ch <= 'z' || ch == '!') {
                        nextChar();
                    }
                    String func = str.substring(startPos, this.pos);
                    x = parseFactor();
                    if (func.equals("sqrt")) {
                        x = Math.sqrt(x);
                    } else if (func.equals("log")) {
                        x = Math.log10(x);
                    } else if (func.equals("ln")) {
                        x = Math.log(x);
                    } else if (func.equals("sin")) {
                        x = Math.sin(Math.toRadians(x));
                    } else if (func.equals("cos")) {
                        x = Math.cos(Math.toRadians(x));
                    } else if (func.equals("tan")) {
                        x = Math.tan(Math.toRadians(x));
                    } else if (func.equals("sinh")) {
                        x = Math.sinh(x);
                    } else if (func.equals("cosh")) {
                        x = Math.cosh(x);
                    } else if (func.equals("tanh")) {
                        x = Math.tanh(x);
                    } else if (func.equals("!")) {
                        int fact = 1;
                        double number = x;
                        for (int i = 1; i <= number; i++) {
                            fact *= i;
                        }
                        x = fact;
                    } else {
                        throw new RuntimeException("Unknown function: " + func);
                    }
                } else {
                    throw new RuntimeException("Unexpected: " + (char) ch);
                }
                return x;
            }
        }.parse();
    }

测试用例:
log(10^3)​​ = 3.0
log(10)^3 = 1.0