How to fix the bug in this expression evaluator?

Question

I found an expression evaluator on stackoverflow at the post: https://stackoverflow.com/a/26227947/8305657

I modified it and added additional functionality to fit my needs. Here is my code:

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();
}

The bug in this expression evaluator seems to be with the exponentiation. For example, if I feed the evaluator the string "sin(sqrt(5))^2", it returns the answer 0.08715574274765818 (in radians), which is incorrect. The correct answer is 0.618974196 (in radians). I found that the reason it is giving the incorrect answer is that it is getting the order of operations wrong when it comes to exponentiation and the built in functions. Rather than evaluating the expression as sin(sqrt(5))^2 like its supposed to, it actually evaluates the expression as sin(sqrt(5)^2). As you can see, rather than doing the exponentiation at the end, it does it in the middle. This problem persists in all the functions. If I use any two functions together and exponentiation at the end, such as log(ln(8))^2 it would still get it wrong.

This problem was there even before I did anything to the original evaluator, since I tested the original code which had the same problem. I have been stuck on this problem for a while, and I don't know how to fix this bug. If someone has a bug fix for this I would greatly appreciate it.

Answer 1

‎Hi parrot15! I'm the writer of the original function. I stumbled on your question randomly ((while vanity searching to see if anyone was using the code)).

It was a non-obvious but deliberate feature of the evaluator as I wrote it that it doesn't require parentheses for function arguments. I did it that way because my pocket calculator accepted it too. So, you can write plain expressions like sqrt 64 and sin 30 + cos 60.

A function simply expects a naked "factor" as its argument. Here is where it gets the function name and evaluates the argument:

String func = str.substring(startPos, this.pos);
x = parseFactor();

So the only reason it accepts parentheses around the function argument is because "factors" can contain parenthesized expressions.

I failed to realize how badly that interacts with exponentiation. Because a factor can also include exponentiation, when you write sin(sqrt(5))^2, everything after sin including the ^2 is a single factor, a single function argument. Definitely unexpected! Without changing the evaluator, you can get the intended result by writing: (sin (sqrt 5))^2.

The simplest fix to the parser is to treat ( specially when this token occurs immediately after a function name. That's how humans would read the expression anyway, and you would also need to do this if you wanted to add support for functions with multiple arguments.

String func = str.substring(startPos, this.pos);
if (eat('(')) {
    x = parseExpression();
    if (!eat(')')) throw new RuntimeException("Missing ')' after argument to " + func);
} else {
    x = parseFactor();
}

(If you prefer, you could make parentheses mandatory for functions, by rejecting the case where eat('(') is false.)

I have now applied this fix in the original posted code. I really wish you had told me about this bug back 4½ years ago!

---

---

The answer by Evan Darke adds "pow" as a new grammar element separate to "factor", and that works well, although note his version also introduces two other changes:

1. My original code parses exponentiation towers like a ^ b ^ c as right-associative: a ^ (b ^ c), which better aligns with the mathematical notation; his version parses it as left-associative (a ^ b) ^ c. You can choose right associativity if desired with a small change inside the parsePow method: if (eat('^')) { x = Math.pow(x, parsePow()); } (calling parsePow instead of parseFactor).

2. My original code parses sin a^b as sin (a^b) (as my calculator interpreted it); his change interprets it as (sin a)^b. I don't see a trivial fix for that, but if you always add explicit parentheses in these cases, as you probably should anyway, then this difference doesn't matter.

Parsers are fun, but they are hard!

Answer 2

It seems to me that the problem is the last line of parseFactor always checks for a ^ operator. so (5)^2 is considered one parseFactor expression, hence sin(5)^2 == sin 25. I think you can solve this by changing the grammar like so:

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

Code:

 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();
    }

Test cases:
log(10^3) = 3.0
log(10)^3 = 1.0