Oh, good point. I forgot about putting stuff afterward. But with the clarification that .* is maximally greedy and %b is minimally greedy, the problem becomes trivial: find the first instance of ")" preceded by a "(" and return that. :P
With a minimally greedy .- so that %b() matches the largest number of parentheses possible, it's still possible to do it in linear time:
1. Find the first instance of ")" preceded by a "(". Return an empty match if not found.
2. Call the position of ( "left" and the position of ) "right". Set depth = 0 and lastGood = right.
3. Increment right.
4. If right goes off the end of the string, return [left ... lastGood].
5. If *right is not ( or ), return [left ... lastGood].
6. If *right == (, increment depth.
7. If *right == ), decrement depth.
8. If depth == 0, lastGood = right.
9. If depth < 0:
9a. Decrement left.
9b. If left < 0, return [0 ... lastGood]
9c. If *left == (, increment depth, lastGood = right.
9d. Else, return [left+1 ... lastGood].
10. Go to 3.
No recursion, no arbitrary backtracking, not even a stack! No character in the input is evaluated more than three times.
/s/ Adam