Efficiently parse single digit arithmetic expressi

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.

Answer 1

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

Answer 2

You need to lookup up 'recursive descent expression parser' or the Dijkstra shunting-yard algorithm. Your present approach is doomed to failure the moment you have to cope with operator precedence or parentheses. You also need to forget about regular expressions and resign yourself to writing a proper scanner.