Calculating infix expression with no parenthesis

Question

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

Simon Forsberg · Accepted Answer · 2014-05-31 10:29:06Z

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++]);
        }
    }
}

And in your switch:

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
– JoJo, Commented May 31, 2014 at 0:06

skiwi · Accepted Answer · 2014-05-31 13:06:42Z

8

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 AddOperator(),
    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.

edited May 31, 2014 at 13:06

skiwi

10.7k6 gold badges44 silver badges108 bronze badges

answered May 30, 2014 at 23:36

rolfl

98.2k17 gold badges220 silver badges419 bronze badges

\$\begingroup\$ 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. \$\endgroup\$

Voo
– Voo

2014-06-01 01:33:44 +00:00
Commented Jun 1, 2014 at 1:33
\$\begingroup\$ 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. \$\endgroup\$

rolfl
– rolfl

2014-06-01 01:42:13 +00:00
Commented Jun 1, 2014 at 1:42
\$\begingroup\$ ♦ 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? \$\endgroup\$

Voo
– Voo

2014-06-01 01:46:36 +00:00
Commented Jun 1, 2014 at 1:46

Add a comment |

vnp · Accepted Answer · 2014-05-31 00:02:11Z

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
– JoJo, Commented May 31, 2014 at 0:12

Stack Exchange Network

Calculating infix expression with no parenthesis

3 Answers 3

You must log in to answer this question.

Hot Network Questions

Calculating infix expression with no parenthesis

3 Answers 3

You must log in to answer this question.

Related

Hot Network Questions