Efficiently parse single digit arithmetic expression

Question

How would you efficiently (optimizing for runtime but also keeping space at a minimum) parse and evaluate a single digit arithmetic expression in Java.

The following arithmetic expressions are all valid:

eval("-5")=-5
eval("+4")=4
eval("4")=4
eval("-7+2-3")=-8
eval("5+7")=12

My approach is to iterate over all elements, keeping track of the current arithmetic operation using a flag, and evaluate digit by digit.

public int eval(String s){
    int result = 0;
    boolean add = true; 
    for(int i = 0; i < s.length(); i++){
        char current = s.charAt(i);
        if(current == '+'){
            add = true;
        } else if(current == '-'){
            add = false;
        } else {
            if(add){
                result +=  Character.getNumericValue(current);
            } else {
                result -= Character.getNumericValue(current);
            }
        }
    }
    return result;
}

Is this the only optimal solution? I have tried to use stacks to keep track of the arithmetic operator, but I am not sure this is any more efficient. I also have not tried regular expressions. I only ask because I gave the above solution in an interview and was told it is sub-optimal.

@KrishnaSarma Yes, that is a possibility given the properties (e.g. eval("+5")=5 or eval("-4")=-4) — stevebot
new ScriptEngineManager().getEngineByExtension("js").eval("-7+4") only because I'm terribly lazy. — sgbj
instead of working with strings you can use vectors, array list, or stack class which optimizes your code further. Generally we don't work with string much as they tend to take up more resources. — Nitesh Verma
@NiteshVerma that's what I have trouble understanding. The only string operations which I am doing seem completely necessary since you have to parse each operation and digit from the string. — stevebot

Jeremy West Jeremy West · Accepted Answer · 2013-09-13T05:03:55

This seems a bit more compact. It certainly requires fewer lines and conditionals. The key is addition is the "default" behavior and each minus sign you encounter changes the sign of what you want to add; provided you remember to reset the sign after each addition.

public static int eval(String s){
    int result = 0;
    int sign = 1; 
    for(int i = 0; i < s.length(); i++){
        char current = s.charAt(i);
        switch (current)
        {
            case '+': break;
            case '-': sign *= -1; break;
            default: 
                result += sign * Character.getNumericValue(current);
                sign = 1;
                break;
        }
    }
    return result;
}

As a note, I don't think yours produces correct results for adding a negative, e.g., "4- -3". Your code produces 1, rather than the correct value of 7. On the other hand, mine allows expressions such as "5+-+-3", which would produce the result 8 (I suppose that's correct? :). However, you didn't list validation as a requirement and neither of us are checking for sequential digits, alpha characters, white space, etc. If we assume the data is properly formatted, the above implementation should work. I don't see how adding data structures (such as queues) could possibly be helpful here. I'm also assuming just addition and subtraction.

These test cases produce the following results:

System.out.println(eval("1+2+3+4"));
System.out.println(eval("1--3"));
System.out.println(eval("1+-3-2+4+-3"));

10
4
-3

Efficiently parse single digit arithmetic expression

2 Answers