Effectively analyze a single-valued arithmetic expression

Question

How would you efficiently (optimizing the runtime, as well as keeping the space at least), analyze and evaluate a unique arithmetic expression in Java.

All valid arithmetic expressions:

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

My approach is to repeat all the elements, track the current arithmetic operation using a flag, and calculate numbers from number to number.

 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 tried using stacks to track the arithmetic operator, but I'm not sure if this is more efficient. I have also not tried regular expressions. I only ask because I gave the above solution in an interview and said that it is not optimal.

Answer 1

It seems a little more compact. This, of course, requires fewer lines and conventions. The key is to add default behavior, and each minus sign that you encounter changes the sign of what you want to add; if you remember the reset 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 side note, I don’t think your results give the correct results for adding a negative value, like “-4 -3”. Your code produces 1, not the correct value 7. On the other hand, mine allows you to express expressions such as "5 + - + - 3", which will lead to result 8 (I assume this is correct? :). However, you did not specify validation as a requirement, and none of us validates consecutive numbers, alpha characters, spaces, etc. If we assume that the data is formatted correctly, the above implementation should work. I do not see how it might be useful to add data structures (like queues). I also assume only addition and subtraction.

These test cases give 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 find a "recursive descent parser" or Dijkstra's bypass algorithm. Your current approach is doomed to failure at the moment when you have to deal with operator priority or parentheses. You also need to forget about regular expressions and come to terms with writing a proper scanner.