Regex Match equal amount of two characters
<p>I'ld like to match the parameters of any function as a string using regex. As an example lets assume the following string:</p>

<pre><code>predicate(foo(x.bar, predicate(foo(...), bar)), bar)
</code></pre>

<p>this may be part of a longer sequence</p>

<pre><code>predicate(foo(x.bar, predicate(foo(...), bar)), bar)predicate(foo(x.bar, predicate(foo(...), bar)), bar)predicate(foo(x.bar, predicate(foo(...), bar)), bar)
</code></pre>

<p>I now want to find all substrings that represent a function/predicate and its parameters (i.e. in the first example the whole string as well as the nested <code>predicate(foo(...), bar)</code>). The problem is that I cant simply match like this</p>

<pre><code>predicate\(.*, bar\)
</code></pre>

<p>as i may then match more than the parameters of the predicate if the <code>*</code> is greedy, or less if it is lazy. Which is because such predicates() can be nested.</p>

<p>I need a regex that finds the string <code>predicate(...)</code> where <code>...</code> matches any string that contains an equal amount of <code>(</code>'s and <code>)</code>'s (lazy).</p>

<p>If it matters: I am using regex with the re module in python.</p>

<p>Adding the <a href="https://pypi.python.org/pypi/regex" rel="nofollow">PyPI package regex</a>, as @Tim Pietzcker suggested, you can use <a href="http://www.regular-expressions.info/recurse.html" rel="nofollow">recursive regexes</a>.</p>

<pre><code>&gt;&gt;&gt; import regex
&gt;&gt;&gt; s = 'predicate(foo(x.bar, predicate(foo(...), bar)), bar)'
&gt;&gt;&gt; pattern = regex.compile(r'(\w+)(?=\(((?:\w+\((?2)\)|[^()])*)\))')
&gt;&gt;&gt; pattern.findall(s)
[('predicate', 'foo(x.bar, predicate(foo(...), bar)), bar'),
 ('foo', 'x.bar, predicate(foo(...), bar)'),
 ('predicate', 'foo(...), bar'),
 ('foo', '...')]
</code></pre>

<p>You could also constrain it to look for just "predicate":</p>

<pre><code>&gt;&gt;&gt; pattern = regex.compile(r'(predicate)(?=\(((?:\w+\((?2)\)|[^()])*)\))')
&gt;&gt;&gt; pattern.findall(s)
[('predicate', 'foo(x.bar, predicate(foo(...), bar)), bar'),
 ('predicate', 'foo(...), bar')]
</code></pre>

python regex first-order-logic