Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Regexp to check if parentheses are balanced [duplicate]

Tags:

java

regex

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.

like image 338
grapescan Avatar asked Oct 12 '10 20:10

grapescan


People also ask

What does '$' mean in regex?

$ means "Match the end of the string" (the position after the last character in the string). Both are called anchors and ensure that the entire string is matched instead of just a substring.

What does regex 0 * 1 * 0 * 1 * Mean?

Basically (0+1)* mathes any sequence of ones and zeroes. So, in your example (0+1)*1(0+1)* should match any sequence that has 1. It would not match 000 , but it would match 010 , 1 , 111 etc. (0+1) means 0 OR 1.

Can a regex identify correct bracketing?

Regular expressions can't count brackets.

Can you use parentheses in regex?

Use Parentheses for Grouping and Capturing. By placing part of a regular expression inside round brackets or parentheses, you can group that part of the regular expression together. This allows you to apply a quantifier to the entire group or to restrict alternation to part of the regex.


2 Answers

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;
}
like image 125
Mark Byers Avatar answered Oct 13 '22 19:10

Mark Byers


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

like image 25
Hank Gay Avatar answered Oct 13 '22 18:10

Hank Gay