# Math expression solver

I've recently stumbled upon an interesting challenge for me:

You should develop C application, that solves math expressions. Operations such as (+,-,*,/) should be supported, as well as (cos, sin, exp). Application should replace constants Pi and E with built-in values. We may have any amount of spaces between operators and braces.

Example:

stdin: 11 + (exp(2.010635 + sin(PI/2)*3) + 50) / 2

stdout: 111.00000 (may have insignificant deviations)

I am interested in solving this problem using Java. I know that the best way is to use lexical analysis or regexp, but for now it is too complex for me. I am trying to solve this task without them. My code works well, but it looks awful, I think.

My code is also on pastebin.

Can you help me make my code style better?

import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;

/**
* Created by Vladimir on 20.02.14.
*/
public class Main {
private static final ArrayList<Character> DIVIDERS = new ArrayList<Character>
(Arrays.asList('*', '/', '-', '+'));
private static final int RIGHT_DIRECTION = 1;
private static final int LEFT_DIRECTION = -1;

public static void main(String[] args) {
String expression = "";

System.out.print("Enter expression: ");
try {
} catch (IOException e) {
e.printStackTrace();
}
System.out.println("Expression: " + expression);

expression = prepareExpression(expression);

System.out.println("Prepared expression: " + expression);

}

//Recursive function with the state machine
//states "(", "sin", "cos", "exp", "*", "/", "+", "-"
private static String calc(String expression) {
int pos = 0;
System.out.println("Solving expression: "+expression);
//Extracting expression from braces, doing recursive call
//replace braced expression on result of it solving
if (-1 != (pos = expression.indexOf("("))) {

String subexp = extractExpressionFromBraces(expression,pos);
expression = expression.replace("("+subexp+")", calc(subexp));

return calc(expression);

//Three states for calculating sin cos exp
//input must be like sin0.7
} else if (-1 != (pos = expression.indexOf("sin"))) {

pos += 2;//shift index to last symbol of "sin" instead of first

String number = extractNumber(expression, pos, RIGHT_DIRECTION);

expression = expression.replace("sin"+number,
Double.toString(Math.sin(Double.parseDouble(number))));

return calc(expression);

} else if (-1 != (pos = expression.indexOf("cos"))) {

pos += 2;

String number = extractNumber(expression, pos, RIGHT_DIRECTION);

expression = expression.replace("cos"+number,
Double.toString(Math.cos(Double.parseDouble(number))));

return calc(expression);

} else if (-1 != (pos = expression.indexOf("exp"))) {

pos += 2;

String number = extractNumber(expression, pos, RIGHT_DIRECTION);

expression = expression.replace("exp" + number,
Double.toString(Math.exp(Double.parseDouble(number))));

return calc(expression);

} else if (expression.indexOf("*") > 0 | expression.indexOf("/") > 0) {

int multPos = expression.indexOf("*");
int divPos = expression.indexOf("/");

pos = Math.min(multPos, divPos);
if (multPos < 0) pos = divPos; else if (divPos < 0) pos = multPos;
//If one value of
//*Pos will be -1 result of min will be incorrect.

char divider = expression.charAt(pos);

String leftNum = extractNumber(expression, pos, LEFT_DIRECTION);
String rightNum = extractNumber(expression, pos, RIGHT_DIRECTION);

expression = expression.replace(leftNum + divider + rightNum,
calcShortExpr(leftNum, rightNum, divider));

return calc(expression);

} else if (expression.indexOf("+") > 0 | expression.indexOf("-") > 0) {

int summPos = expression.indexOf("+");
int minusPos = expression.indexOf("-");

pos = Math.min(summPos, minusPos);

if (summPos < 0) pos = minusPos; else if (minusPos < 0) pos = summPos;

char divider = expression.charAt(pos);

String leftNum = extractNumber(expression, pos, LEFT_DIRECTION);
String rightNum = extractNumber(expression, pos, RIGHT_DIRECTION);

expression = expression.replace(leftNum + divider + rightNum,
calcShortExpr(leftNum, rightNum, divider));

return calc(expression);

} else return expression;
}

private static String extractExpressionFromBraces(String expression, int pos) {
int braceDepth = 1;
String subexp="";

for (int i = pos+1; i < expression.length(); i++) {
switch (expression.charAt(i)) {
case '(':
braceDepth++;
subexp += "(";
break;
case ')':
braceDepth--;
if (braceDepth != 0) subexp += ")";
break;
default:
if (braceDepth > 0) subexp += expression.charAt(i);

}
if (braceDepth == 0 && !subexp.equals("")) return subexp;
}
return "Failure!";
}

private static String extractNumber(String expression, int pos, int direction) {

String resultNumber = "";
int currPos = pos + direction;//shift pos on next symbol from divider

//For negative numbers
if (expression.charAt(currPos) == '-') {
resultNumber+=expression.charAt(currPos);
currPos+=direction;
}

for (; currPos >= 0 &&
currPos < expression.length() &&
!DIVIDERS.contains(expression.charAt(currPos));
currPos += direction) {
resultNumber += expression.charAt(currPos);
}

if (direction==LEFT_DIRECTION) resultNumber = new
StringBuilder(resultNumber).reverse().toString();

return resultNumber;
}

private static String calcShortExpr(String leftNum, String rightNum, char divider) {
switch (divider) {
case '*':
return Double.toString(Double.parseDouble(leftNum) *
Double.parseDouble(rightNum));
case '/':
return Double.toString(Double.parseDouble(leftNum) /
Double.parseDouble(rightNum));
case '+':
return Double.toString(Double.parseDouble(leftNum) +
Double.parseDouble(rightNum));
case '-':
return Double.toString(Double.parseDouble(leftNum) -
Double.parseDouble(rightNum));
default:
return "0";
}

}

private static String prepareExpression(String expression) {

expression = expression.replace("PI", Double.toString(Math.PI));
expression = expression.replace("E", Double.toString(Math.E));
expression = expression.replace(" ", "");

return expression;
}
}


I agree with that a different approach would be better, so just a few random notes, mostly about the current code:

1. It's good to know that it's already in the JDK, in form a script engine. So, if you don't want to reinvent the wheel just use it:

import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;

final ScriptEngineManager engineManager = new ScriptEngineManager();
final ScriptEngine engine = engineManager.getEngineByName("JavaScript");
String expression = "11 + (Math.exp(2.010635 + Math.sin(Math.PI/2)*3) + 50) / 2";
System.out.println(engine.eval(expression)); // prints 110.99997794278411


The syntax is not the same (you need the Math. prefix) but I guess it can be changed.

2. Instead of doubles (and floating point numbers) consider using BigDecimals. Floating point numbers are not precise. Here is an example:

Enter expression: 1.03-0.42
Expression: 1.03-0.42
Prepared expression: 1.03-0.42
Solving expression: 1.03-0.42
Solving expression: 0.6100000000000001


(It might not fit well for trigonometric functions.)

3. DIVIDERS currently mutable. You could wrap it with Collections.unmodifiableList to avoid accidental modification. A more compact form is Guava's ImmutableList:

private static final List<Character> DIVIDERS = ImmutableList.of('*', '/', '-', '+');

4. In some places I would use aString.contains instead of indexOf. It's more meaningful, closer to the English language, easier to read since you cat get rid of the comparison. In conditionals like this

expression.indexOf("*") > 0 | expression.indexOf("/") > 0


I'd use the even more compact

StringUtils.containsAny(expression, "*/")

5. The following lines also could be replaced with StringUtils:

int multPos = expression.indexOf("*");
int divPos = expression.indexOf("/");

pos = Math.min(multPos, divPos);
if (multPos < 0)
pos = divPos;
else if (divPos < 0)
pos = multPos;

pos = StringUtils.indexOfAny(expression, "*/")


It's the same.

6. Instead of returning with an error string, like

return "Failure!";


I think you should throw an exception and stop the processing immediately, there is no point to "continue" the processing with wrong subresult (or to pretend that it continues). (The Pragmatic Programmer: From Journeyman to Master by Andrew Hunt and David Thomas: Dead Programs Tell No Lies.)

The same is true for the default branch of calcShortExpr. If you call it with an invalid "divider" it's definitely an error in the program and it should stop.

7. The divider variable actually contains the operator which is a little bit confusing. I'd rename it for better readability.

You're right that a proper expression parser would be the superior approach. Nevertheless, your ad hoc solution works surprisingly well, though it will have some odd behaviour.

I'll just start by pointing out that your exception handling in main() is shaky. If you get an IOException, you'll print a stack trace, then proceed to evaluate an empty string anyway.

What you probably want to do if there is an IOException is to skip the rest of the program:

try {
System.out.println("Expression: " + expression);
expression = prepareExpression(expression);
System.out.println("Prepared expression: " + expression);
} catch (IOException e) {
e.printStackTrace();
}


In this particular case, since all you do is print a stack trace and abort, you could just take advantage of Java's default behaviour. All you have to do is declare that main() can throw an IOException.

public static void main(String[] args) throws IOException {

System.out.print("Enter expression: ");
System.out.println("Expression: " + expression);

expression = prepareExpression(expression);
System.out.println("Prepared expression: " + expression);


For example, with the following input: -8 + 3. The program enters the function (see stacktrace below) and fails to execute the calculation.
java.lang.StringIndexOutOfBoundsException: String index out of range: -1