How to fix the bug in this expression evaluator?
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.
Solution 1:
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