Regexp to check if parentheses are balanced

Question

Possible Duplicate:
Can regular expressions be used to match nested patterns?

I am writing a regexp to check if the input string is a correct arithmetic expression. The problem is checking if there are enough opening and closing parentheses.

Expressions:

1. (1)

2. (((1)

3. ((1))))

I think lookahead and lookbehind are useful here but for now I could check only one kind. I'm using Java, if it matters.

Answer 1

You shouldn't use regular expression to do this. Instead you can iterate over the string character by character and keep track of the nesting level.

Initially the nesting is 0. When you see a ( increase the nesting by 1, and when you see ) decrease the nesting. The expression is correctly balanced if the final nesting is 0 and the nesting never goes below 0.

public static boolean checkParentheses(String s) {
    int nesting = 0;
    for (int i = 0; i < s.length(); ++i)
    {
        char c = s.charAt(i);
        switch (c) {
            case '(':
                nesting++;
                break;
            case ')':
                nesting--;
                if (nesting < 0) {
                    return false;
                }
                break;
        }
    }
    return nesting == 0;
}

Answer 2

You need to be using a parser to do this, not a regex. See this question.

Answer 3

Why not just count the opening and closing parens like so?

String expression = "((1+x) - 3 * 4(6*9(12+1)(4+(2*3+(4-4)))))";

int open = 0;
for(int x = 0; x < open; x++){
   if(expression[x] == '(')
      open++;
   else if(expression[x] == ')')
      open--;
}
if (open != 0)
   // Not a valid expression

Of course this only checks that you have the right amount - someone could write '))3*4((' and it would be validated using this method.