Way of processing a string of plus and minus operations

Question

Hello,

I'm writing a java method that takes a string of plus and minus operations, eg

"+1+2+3-5" and I want it to return an int of the answer.

I'm trying to do this as efficiently as possible. I've tried the String.split() method, but it gets slightly confusing with the pluses and minuses.

Can anyone help? No, this isn't homework.

Answer 1

Have a look at "RPN Calculator" for a good starting point.

Answer 2

You are going to need to parse the string character by character. Something like

int foo(String s){  
    int total = 0;
    String currentNum = ""  
    for(int i =0;i<s.length;i++){   
        if(s[i] =="+"){   
           total += Integer.parseInt(currentNum);   
           currentNum = ""   
        }else if(s[i] =="-"){  
           total -= Integer.parseInt(currentNum);  
           currentNum = ""  
        }else{   
           currentNum += s[i]   
        }   
     }     
     return total;
}

Answer 3

Well, a few things to think about...

• You could potentially use split to help with the parsing, but you'll need the separators as well the numbers
• You could scan through the string, remembering where the start of the current number is and then parsing it when you've found the end.
• What data structures are you going to use to store the string after you parse it?
  • You may want to consider that subtracting 20 is like adding -20...
  • ... or you may want to think about alternating between number and operator, starting with an implicit "+" if the first character isn't "-"
• You should strongly consider splitting the task up into the "parsing" and "evaluating" phases. In particular, you should be able to write tests for the evaluation phase even without writing any parsing code - and vice versa.
• You say you want to do this as efficiently as possible - why? Efficiency is often (but certainly not always) the enemy of clarity. I would at least try to go for a clear solution first and then work out how efficient it is. Often a clear solution will be "efficient enough".

Answer 4

The shunting yard algorithm is what you need here and it should be pretty easy to implement it in Java.

Answer 5

Generally with these types of problems, you need a binary tree. However, your case is simpler, and you can use regex.

Pattern pattern = Pattern.compile("([+-]?)([\\d]+)");
String str = "+10-3+20-10-20";
Matcher m = pattern.matcher(str);
while (m.find()) {
    System.out.println(m.group(1));
    System.out.println(m.group(2));
}

This piece of code gives you all the signs (group(1)) and all the numbers (group(2)) Now you should only complete the while-loop with the proper if-clauses.