Take the 2-minute tour ×

I am going to write an expression evaluator which only does addition and subtraction. I have a simple algorithm to do that; but, I have some implementation problems.

I considered an expression as (it is a String)

"(" <expression1> <operator> <expression2> ")"

Here is my algorithm

String evaluate( String expression )

   if expression is digit
      return expression

   else if expression is "(" <expression1> <operator> <expression2> ")"
      cut the brackets out of it
      expression1 = evaluate( <expression1> )
      operator = <operator>
      expression2 = evaluate( <expression2> )

   if operator is +
      expression1 + expression2

   else if operator is -
      expression1 - expression2 

My problem is parsing <expression1>, <operator> and <expression2> from the expression. How can I do that?

Note: I'm not asking for a code. All I need is an idea to do that.

Thank you,


share|improve this question
If you are interested in a working example of a small Java math evaluator written in precisely this way, I have one on my website: softwaremonkey.org/Code/MathEval –  Lawrence Dol Nov 2 '10 at 0:16

6 Answers 6

up vote 7 down vote accepted


Don't do that, then :) When you see an opening bracket, do your recursive call to expression. At the end of the expresssion, either you find another operator (and so you're not at the end of the expression after all), or a right-bracket, in which case you return from the evaluate.

share|improve this answer
Well, to do a recursive call to parse expression1, he would basically need to count parenthesis in order to tell where expression1 ended, but otherwise I like your answer. –  aioobe Nov 1 '10 at 21:26
Not really. The recursion does the counting for you. If you run across a ) at a point where an expression could end, that's the end of this recursive call. This is how recursive-descent parsers work... –  Paul Nov 1 '10 at 21:28
Ah, so you recurse on the tail of the string, even if it's ill-balanced? –  aioobe Nov 1 '10 at 21:36
I think so, if I understand you correctly. If you see a (, you recurse. Either you hit the end of the input (in which case, error) or you see a balancing ) and return from this recursion. If you see a ) after returning to the top level, that's an error too. This is what (recursive descent) parser generators will produce, but it's educational to implement one yourself. That's why they're called recursive descent, in fact! –  Paul Nov 1 '10 at 21:45
Yes, I wrote a recursive descent parser in Java for math expression in this way, recognizing that any expression enclosed in parentheses was simply a sub-expression which can be handled by a recursive call. However, I skipped to the matching closing parenthesis when I found the opening one and the recursive call considered only the enclosed string. It would have been more efficient to recognize ')' as an end-of-expression and return the sub-expression result at that point. –  Lawrence Dol Nov 2 '10 at 0:19

Either you use a parser generator such as JavaCUP or ANTLR. Write up a BNF of your expression and generate a parser. Here is a sample grammar that would get you started:

Expression ::= Digit
            |  LeftBracket Expression Plus Expression RightBracket
            |  LeftBracket Expression Minus Expression RightBracket
            |  LeftBracket Expression RightBracket

A "hacky" way of doing it yourself would be to look for the first ) backtrack to the closest ( look at the parenthesis free expression in between, simply split on the operator symbols and evaluate.

share|improve this answer
+1 for CUP.. :) –  Joseph Weissman Nov 1 '10 at 21:21
I think you left Number out of your grammar. –  msandiford Nov 1 '10 at 21:26
Oh, of course, thanks spong. Updated. –  aioobe Nov 1 '10 at 21:29
That’s an ambiguous grammar, since parentheses aren’t mandatory. –  Josh Lee Nov 1 '10 at 21:30
Good point. And the OP seemed to require parentheses so I added it :-) –  aioobe Nov 1 '10 at 21:38

I would recommend changing the infix input into postfix and then evaluating it, rather than reducing the expression infix-wise. There are already well defined algorithms for this and it doesn't come with the inherent multiple-nested-parentheses parsing problems.

Take a look at the Shunting Yard Algorithm to convert to postfix/RPN then evaluate it using a stack using Postfix Operations. This is fast (O(n)) and reliable.


share|improve this answer
This one is easy and straightforward. +1. –  belisarius Nov 1 '10 at 23:46

Use a StringTokenizer to split your input string into parenthesis, operators and numbers, then iterate over your tokens, making a recursive call for every open-parens, and exiting your method for every close parenthesis.

I know you didn't ask for code, but this works for valid input:

public static int eval(String expr) {
    StringTokenizer st = new StringTokenizer(expr, "()+- ", true);
    return eval(st);

private static int eval(StringTokenizer st) {
    int result = 0;
    String tok;
    boolean addition = true;
    while ((tok = getNextToken(st)) != null) {
        if (")".equals(tok))
            return result;
        else if ("(".equals(tok))
            result = eval(st);
        else if ("+".equals(tok))
            addition = true;
        else if ("-".equals(tok))
            addition = false;
        else if (addition)
            result += Integer.parseInt(tok);
            result -= Integer.parseInt(tok);
    return result;

private static String getNextToken(StringTokenizer st) {
    while (st.hasMoreTokens()) {
        String tok = st.nextToken().trim();
        if (tok.length() > 0)
            return tok;
    return null;

It would need better handling of invalid input, but you get the idea...

share|improve this answer
I didn't understand why did you use getNextToken() instead of using nextToken() ? –  Alican Ozgoren Nov 1 '10 at 22:30
ah, sorry, I got it now. :) I think it is what paul suggested me to do... –  Alican Ozgoren Nov 1 '10 at 22:33
It doesn't handle parentheses or operator precedence correctly, and it never will until you introduce recursion into it, or an operand stack. –  EJP Nov 2 '10 at 6:44
Parenthesis are handled correctly, and since addition and subtraction (the only 2 operations needed) have the same precedence, there's no need to add any additional logic for that. If you were to want multiplication and division, then yes, you'd need an operand stack. –  Luke Hutteman Nov 2 '10 at 13:05
@ECP: Mea Culpa - I see you're right about the mishandling of parenthesis; my unnecessary recursive call for simple addition or subtraction was messings things up there... that's what I get for trying to hack some code together in 5 minutes :p I fixed the code to remove this unnecessary recursion. –  Luke Hutteman Nov 2 '10 at 19:10

I would suggest taking an approach that more closely resembles the one described in this old but (in my opinion) relevant series of articles on compiler design. I found that the approach of using small functions/methods that parse parts of the expression to be highly effective.

This approach allows you to decompose your parsing method into many sub-methods whose names and order of execution closely follows the EBNF you might use to describe the expressions to be parsed.

share|improve this answer

Perhaps create regular expressions for expression and operator and then use matching to identify and break out your content.

share|improve this answer
You can't create a regular expression for expression as it involves well balanced parentheses. –  aioobe Nov 1 '10 at 21:28
Good luck balancing the parentheses with a regexp... –  Paul Nov 1 '10 at 21:28
This is not a regular language, it is context free and so cannot be parsed by regular expressions. –  Callum Rogers Nov 1 '10 at 21:58

Your Answer


