# Calculating infix expression with no parenthesis

This is my Java implementation ($O(n)$) about how to calculate infix expression with no parenthesis.

For example, when we input "3 + 4 * 4 / 8", we will get a double type answer is 5.0. Here to make the algorithm simple, we don't consider any parenthesis in the expression.

I think my implementation is kind of tedious and long. Can anyone give me some advice on making it cleaner?

public double computeInfixExpr(String input) {
String[] expr = input.split(" ");
int i = 0;
double operLeft = Integer.valueOf(expr[i++]);
while (i < expr.length) {
String operator = expr[i++];
double operRight = Double.valueOf(expr[i++]);
switch (operator) {
case "*":
operLeft = operLeft * operRight;
break;
case "/":
operLeft = operLeft / operRight;
break;
case "+":
while (i < expr.length) {
String operator2 = expr[i++];
if (operator2.equals("+") || operator2.equals("-")) {
i--;
break;
}
if (operator2.equals("*")) {
operRight = operRight * Double.valueOf(expr[i++]);
}
if (operator2.equals("/")) {
operRight = operRight / Double.valueOf(expr[i++]);
}
}
operLeft = operLeft + operRight;
break;
case "-":
while (i < expr.length) {
String operator2 = expr[i++];
if (operator2.equals("+") || operator2.equals("-")) {
i--;
break;
}
if (operator2.equals("*")) {
operRight = operRight * Double.valueOf(expr[i++]);
}
if (operator2.equals("/")) {
operRight = operRight / Double.valueOf(expr[i++]);
}
}
operLeft = operLeft - operRight;
break;
}
}
return operLeft;
}


There is one big section of code duplication in your code. The cases for + and - are almost identical.

There are a couple of solutions to solve this, one of them is to put them at the same case label and use an if for the small part that is different:

case "+":
case "-":
while (i < expr.length) {
String operator2 = expr[i++];
if (operator2.equals("+") || operator2.equals("-")) {
i--;
break;
}
if (operator2.equals("*")) {
operRight = operRight * Double.valueOf(expr[i++]);
}
if (operator2.equals("/")) {
operRight = operRight / Double.valueOf(expr[i++]);
}
}
if (operator.equals("+")) {
operLeft = operLeft + operRight;
}
else {
operLeft = operLeft - operRight;
}
break;


Another alternative is to extract method with the common parts:

SomeReturnType someMethod(SomeParameterTypes someParameters...) {
while (i < expr.length) {
String operator2 = expr[i++];
if (operator2.equals("+") || operator2.equals("-")) {
i--;
break;
}
if (operator2.equals("*")) {
operRight = operRight * Double.valueOf(expr[i++]);
}
if (operator2.equals("/")) {
operRight = operRight / Double.valueOf(expr[i++]);
}
}
}


case "+":
someMethod(...);
operLeft = operLeft + operRight;
break;
case "-":
someMethod(...);
operLeft = operLeft - operRight;
break;


When writing this method, be aware that primitive types passed as arguments to a method are passed by value, not by reference. You need to think of a smart way to return the results of this method. To return more than one thing, you can return an object.

return new CalcResult(operLeft, operRight);


However, you should really consider a different approach, such as the one @rolfl has suggested.

• you are right. If I extract to some method, it will come up to another problem. For example, someMethod(...), need return two return values, one is operRight, and another is i. Java cannot do this perfectly. It is quite annoying. @Simon André Forsberg
– JoJo
Commented May 31, 2014 at 0:06

It is common, when processing things like this, to use a chain-of-responsibility pattern.

In this case, you can create an operator interface, or abstract class:

public interface BinaryOperator {
public boolean isOwner(String operator);
public double operateOn(double left, double right);
}


Then, you create an instance of that interface for each operator you support like the following for 'add':

public class AddOperator implements BinaryOperator {
public boolean isOwner(String op) {
return "+".equals(op);
}

public double operateOn(double left, double right) {
return left + right;
}
}


Then, you create an instance for all your supported operators, and then put them in to an array, in precedence order (if you support precedence).

It will look like:

private static final BinaryOperator OPERATORS = {
new MultiplyOperator(),
....
new SubtractOperator()
}


and, in your parsing/handling code, you do the following:

public double handle(double left, String parsedOp, double right) {
for (BinaryOperator op : OPERATORS) {
if (op.isOwner(parsedOp)) {
return op.operateOn(left, right);
}
}
throw new UnsupportedOperationException("Can't handle " + parsedOp);
}


This will drastically simplify your code, and it will make it much easier to support other operations too.

• A HashMap<String, BinaryOperator> would seem the more obvious solution here instead of going for the isOwner version. Shorter and how the parser represents an addition shouldn't matter for the actual class.
– Voo
Commented Jun 1, 2014 at 1:33
• I specifically chose the array @Voo because it is ordered, and can help with precedence. You can loop through your operators, process them in precedence order. Commented Jun 1, 2014 at 1:42
• ♦ But as I understand it you always only check which class can parse the next operator, so I don't see how this has anything to do with precedence. If we base this off the shunting yard algorithm (which seems the obvious approach), we would also just go through all seen operators in order - what algorithm do you have in mind where we'd do it differently?
– Voo
Commented Jun 1, 2014 at 1:46

First thing you'd want to do is to eliminate repetitive code (aka copy-paste) from case "*" and case "-" and replace it with the method. These loops compute the value of what is known as term, hence the name of the method should be computeTerm.

An interesting question is what the return value of computeTerm should be: it shall return both the value of the term and an index of first unprocessed token. To make things really simple you should realize that a single number (a *primary expression, in fact) is itself a term.

Consider the following pseudocode for computing expression:

index = 0;
value, index = computeTerm(expr, 0);
while (index < expr.length) {
operator = expr[index++]);
operand, index = computeTerm(expr, index);
switch (operator) {
case "+":
value += operand;
break;
case "-":
value -= operand;
break;
default:
return value, index;
}
}


Computing term is essentially the same code: the only difference is that it cares about different operators.

• that's my question. However, java cannot allow method to return two values. @vnp
– JoJo
Commented May 31, 2014 at 0:12
• How about returning a class having two (public) values?
– vnp
Commented May 31, 2014 at 0:32