Regexp to check if parentheses are balanced

Question

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

I am writing a regular expression to check if the input string is a valid arithmetic expression. The problem is checking for enough opening and closing parentheses.

Expressions:

• (one)

• (((one)

• ((one))))

I think lookahead and lookbehind are useful here, but at the moment I can only check one view. I use Java if that matters.

Answer 1

You should not use regex for this. Instead, you can iterate over the character of a string by character and track the level of nesting.

Initially, nesting is 0. When you see ( , increase nesting by 1, and when you see ) , reduce nesting. The expression is correctly balanced if the final nesting is 0, and the nesting never drops 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

To do this, you need to use a parser, not a regular expression. See this question .

Answer 3

Why not just consider opening and closing guys like that?

 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 correct amount - someone can write ')) 3 * 4 ((' and it will be checked using this method.