regular expression to find all starting brace has an ending brace

Question

I need an regular expression to find all starting brace has an ending brace. Suppose

([(([[(([]))]]))]) -- this one will return true. but
[](()()[[]])[][[([]) --- this one will return false

for this, I've tried below:-

function check($str) {
    $output = "";
    $pattern = "/(\{[^}]*)([^{]*\})/im";
    preg_match($pattern, $str, $match);
    print_r($match[0]);
}

assert(check("[](()()[[]])[][[([])") === FALSE);

any help please...

Standard regular expressions can't do this, because they can't count or recurse. Perl has a recursion extension that can do this, but PHP uses PCRE, which doesn't. — Barmar, Mar 12 '14 at 12:45
If I understand well, you want to obtain false if brackets are not balanced? Should `)(` return `true`? — Casimir et Hippolyte, Mar 12 '14 at 12:46
possible duplicate of [regular expression to match nested braces](http://stackoverflow.com/questions/2778532/regular-expression-to-match-nested-braces) — Barmar, Mar 12 '14 at 12:46
@Barmar so how and which method - I'll achieve this? any help please... — Ripa Saha, Mar 12 '14 at 12:47
@Barmar: It is not a duplicate of this question. In the example above there are different types of brackets. — Casimir et Hippolyte, Mar 12 '14 at 13:19

score 1 · Answer 1 · answered Mar 12 '14 at 12:55

The easiest way to do this (in my opinion) would be to implement a stack data structure and pass through your string. Essentially something like so:

Traverse the string left to right
If you find an opening parenthesis, add it to the stack
else (you find a closing parenthesis) make sure that the top most item in the stack is the same type of parenthesis (so make sure that if you found a }, the top most item in the stack is {). This should help scenarios where you have something like so: ({)}. If it matches, pop from the stack.

If you repeat the above operation throughout the entire string, you should end up with an empty stack. This would mean that you have managed to match all open parenthesis with a close parenthesis.

Casimir et Hippolyte · Answer 2 · 2014-03-12T14:11:01.387

You can use this:

$pattern = '~^(\((?1)*\)|\[(?1)*]|{(?1)*})+$~';

(?1) is a reference to the subpattern (not the matched content) in the capture group 1. Since I put it in the capture group 1 itself, I obtain a recursion.

I added anchors for the start ^ and the end $ of the string to be sure to check all the string.

Note: If you need to check a string that contains not only brackets, you can replace each (?1)* with:

(?>[^][}{)(]++|(?1))*

Note 2: If you want that an empty string return true, you must replace the last quantifier + with *

Working example:

function check($str, $display = false) {
    if (preg_match('~^(\((?1)*\)|\[(?1)*]|{(?1)*})+$~', $str, $match)) {
        if ($display) echo $match[0];
        return true;
    }
    elseif (preg_last_error() == PREG_RECURSION_LIMIT_ERROR) {
        if ($display) echo "The recursion limit has been reached\n";
        return -1;
    } else return false;
}

assert(check(')))') === false);

check('{[[()()]]}', true);

var_dump(check('{[[()()]]}'));

regular expression to find all starting brace has an ending brace

2 Answers2