Question for regex gurus

Question

Perl

Is there a way to check the balance of brackets in strings like ((()(()()))()) using regular expressions? Personally, I don't know of such a way. Maybe I don't know something?

Answer 1

First, remove all non-brackets from the string (that is, find the regular expression “ [^()] ” and replace it with an empty string), then go from regular expressions to ordinary programming - go through the final line of brackets in a character-by-character loop, which to the value of some variable ( initially having a zero value) adds one if the symbol “ ( ” is found and subtracts one if the symbol “ ) ” is found, and the loop ends immediately if the value is less than zero (an imbalance of brackets is found), and at the end of the loop (which corresponds to the end of the line brackets), this value must also be equal to zero, otherwise, again, an imbalance of brackets is found.

Answer 2

Recursive expressions work
\( (?: [^()] *+ | (?0) )* \)
in some languages: You can cheat in some languages ​​(PERL):

$regex = qr/
  \(
    (
      [^()]+
    |
      (??{$regex})
    )*
  \)
/x;

(Ruby)

re = %r{
  (?<re>
    \(
      (?:
        (?> [^()]+ )
        |
        \g<re>
      )*
    \)
  )
}x

Answer 3

Even if it is possible, then you should not check it with them, with the help of the stack it will all go faster, easier and more understandable.

Answer 4

In PHP:
$balanced = !preg_match("/[()]/", preg_replace("/\((((?>[^()]+)|(?R))*)\)/", " ", $string));
It including for lines of a look: aaa(bb)cc
But it is a perversion, it is better to do as Mithgol wrote.

Answer 5

It is better not to do it through regular expressions. See also Chomsky hierarchy and here .

Answer 6

This problem is unsolvable in regular expressions and in finite automata (equivalent means), it requires a push-down automaton, that is, a stack. Although if the maximum depth of brackets is limited, then some ugly solution can probably be invented.

Answer 7

Regexp is not the means by which you need to solve such a problem. They are not designed to work with nested/recursive structures.
Theoretically, of course, you can go crazy and come up with a solution. It all depends on how "smart" the algorithm should be.
The correct solution for the simple case (when nothing else is required other than bracket checking) is a simple function in your favorite language that counts brackets. For more advanced cases, a library for lexical / parsing.

Answer 8

Well, as an option, you can use this expression \((?=[^\(]*\)).*?\) to consistently replace all brackets with spaces (it removes the most nested bracket), and then search in the string "(" or ")", if found, means the balance of the curve.
But it's easier to balance two counters and one pass along the line :)