Write a function that checks if the parentheses of an expression match.

The task involves several types of brackets: [], () and {}. For example, the parenthesis in this expression match:

({[12][34]}{(56)})While in this expression they do not:

{[909)I wrote a test function (in PHP):

function test(string $exp, bool $expected) { if (matchBrackets($exp) !== $expected) { echo "Error matching " . $exp . "\n"; } }and some tests

test("()", true); test("()()", true); test("noot()noot", true); test("(aap)", true); test("aap", true); test("(", false); test(")", false); test("{[]}", true); test("{[][]}", true); test("{[]()}", true); test("", true); test("{[aap](({banaan}))}", true); test("{[{[](({}){a[](({}))}){b[](({})){[](({c}))}}{[](({}))}}]({[]d(({}){[](({123}))})}({{[](({}))}}))}", true); test("{[aap](({banaa))}", false); test("{[aap]((anaan}))}", false);

Solving the problem in an elegant way requires you to use recursive nature of the domain.

While the developer was writing the program, I tried to figure it out for myself. And it occurred to me that next to some algorithmic options, there would also be a possibility to use a regular expression. But this could only be done by applying the advanced

*recursive patterns*feature. I had heard of this feature, but never used it.

I would certainly not demand of the developer to give such an answer, but it intrigued me too much to let it go.

It is indeed possible, and so, without further ado, I present the answer here:

function matchBrackets(string $exp): bool { return preg_match('/^ # start of group 1 ( ( ( [^\(\{\[\)\}\]]+ ) | ( \( (?1) \) ) | ( \[ (?1) \] ) | ( \{ (?1) \} ) )* ) $/x', $exp); }

//xThe "x" modifier strips all whitespace from the string. This allows you to make it more readable.

/^$/xMatch the beginning and end of $exp.

/^(Create the group that will be used for recursion.)$/xrecursion-group

/^((Each item in this group can be repeated any number of times. This also allows for the completely empty $exp.)*)$/xrecursion-group

/^(((Any nested group consists of a sequence of non-brackets, or a set of round brackets () or a set of squared brackets [] or a set of curly braces {}. Finally a "bracket" groups look like this:)|(other-chars)|(round-brackets)|(squared-brackets))*)$/xcurly-braces

\{ (?1) \}It starts with a bracket (here "{"), followed by a recursive group, and ends with the matching bracket "}"..

A recursive group can repeat the entire expression. You would have to use (?R) in stead of (?1). Here it just matches a single group (group 1) from the expression. Group 1 is the group that starts with the first "(" in the expression. I do not use (?R) here because that would place the ^ and $ in the middle of the expression. That would never give a match.

## Geen opmerkingen:

## Een reactie posten