Splitting input string for a calculator

Question

I'm trying to split the input given by the user for my calculator. For example, if the user inputs "23+45*(1+1)" I want to this to be split into [23,+,45,*,(,1,+,1,)].

Answer 1

What your looking for is called a lexer. A lexer splits up input into chunks (called tokens) that you can read.

Fortunately, your lexer is pretty simple and can be written by hand. For more complicated lexers, you can use flex (as in "The Fast Lexical Analyzer"--not Adobe Flex), or (since you're using Java) ANTLR (note, ANTLR is much more than just a lexer).

Simply come up with a list of regular expressions, one for each token to match (note that since your input is so simple, you can probably do away with this list and merge them all into one single regex. However, for more advanced lexers, it helps to do one regex for each token) e.g.

\d+
\+
-
*
/
\(
\)

Then start a loop: while there are more characters to be parsed, go through each of your regular expressions and attempt to match them against the beginning of the string. If they match, add the first matched group to your list of input. Otherwise, continue matching (if none of them match, tell the user they have a syntax error).

Pseudocode:

List<String>input = new LinkedList<String>();
while(userInputString.length()>0){
    for (final Pattern p : myRegexes){
        final Matcher m = p.matcher(userInputString);
        if(m.find()) {
            input.add(m.group());
            //Remove the token we found from the user's input string so that we
            //can match the rest of the string against our regular expressions.
            userInputString=userInputString.substring(m.group().length());
            break;
        }
    }
}

Implementation notes:

• You may want to prepend the ^ character to all of your regular expressions. This makes sure you anchor your matches against the beginning of the string. My pseudocode assumes you have done this.

Answer 2

I think using stacks to split the operand and operator and evaluate the expression would be more appropriate. In the calculator we generally use Infix notation to define the arithmetic expression.

Operand1 op Operand2

Check the Shunting-yard algorithm used in many such cases to parse the mathematical expression. This is also a good read.