Matching braces puzzle

Question

While I was working, I found a nice puzzle that asked to create a function that matches the braces correctly for {, (, [ with their corresponding braces ], ), }

An example of an expression they provided was the following:

$expressions = array(")(){}","[]({})","([])","{()[]}","([)]");

The values that must be returned are:

0
1
1
1
0

The constraints they provided is that the strings are going to have a maximum a length of 100, and the array may carry at least 50,000 elements. Given those cases, they expect the function to solve the problem in less than 2 seconds.

I tried to write something up, which can be found here (it is incomplete because I felt that this whole if/else method is making it all too hairy - in other words, it would definitely take more than 2 seconds to solve the problem):

https://gist.github.com/adibbehjat/6387415

<?php

function check_braces($expressions) {

    for($x = 0; $x < count($expressions); $x++)
    {
        $open = array("{", "[", "(");
        $close = array("}", "]", ")");
        $key = array("{" => "}", "[" => "]", "(" => ")");
        $string = $expressions[$x];
        echo $string."<br>";

        //First item should open a brace, else fail
        if((in_array($string[0], $close)) && (strlen($string) % 2))
        {
            echo 0;
            echo '<br>';  
        }
        else
        {
            $bank_o = array();
            $bank_c = array();
            $element = array();

            for($y = 0; $y < strlen($string); $y++)
            {
                $element = $string[$y];

                if(in_array($element, $open))
                {
                    array_push($bank_o, $element);
                }
                else
                {
                    array_push($bank_c, $element);
                }

                $arraycounter = array_merge($bank_o, $bank_c);

                $y++;

                if(!empty($bank_c) && !empty($bank_o))
                {
                    $num = count($bank_o);
                    if($bank_c[0] == $key[$bank_o[$num - 1]])
                    {
                        array_shift($bank_c);
                        array_pop($bank_o);
                    }
                }
                elseif (empty($bank_c) && empty($bank_o)) {
                    echo 1 . "<br>";
                }
                else
                {

                }

            }
        }
    }
}

//$expressions = array(")(){}","[]({})","([])","{()[]}","([)]");

$expressions = array("([])","([)]");

check_braces($expressions);

?>

I learned PHP on my own, and feel that I am lacking a lot of skill in identifying best algorithms to solve such problems. And was curious to see what other alternative methods are possible.

@deceze Sorry. That's a grammatical error. But, what I meant in regards to 0,1,1,1,0 are the binary confirmations; 0 being false and 1 being true. 0 being that the braces are incorrectly matched, and 1 being that they are correctly matched. — Adib, Aug 30 '13 at 08:20
http://stackoverflow.com/questions/12752225/how-do-i-find-the-position-of-matching-parentheses-or-braces-in-a-given-piece-of — exussum, Aug 30 '13 at 08:24
When you have to deal with recursive braces like this, don't use regex. See this answer for example; http://stackoverflow.com/questions/524548/regular-expression-to-detect-semi-colon-terminated-c-for-while-loops/524624#524624 except you need to adjust it so that it takes validness in consideration. — Gerben Jacobs, Aug 30 '13 at 08:24
Ah, so the problem description can be reduced to "check if a given expression has matching braces, yes or no". That's pretty darn simple with a state machine and a stack. — deceze, Aug 30 '13 at 08:25

deceze · Accepted Answer · 2013-08-30T08:52:52.427

3

<?php

function checkMatchingBraces($expression) {
    static $braces = [
        '(' => ')',
        '{' => '}',
        '[' => ']'
    ];
    $stack = [];
    $state = null;  // $state is only used for efficiency,
                    // would need to call end($stack) a lot otherwise

    for ($i = 0, $length = strlen($expression); $i < $length; $i++) {
        $char = $expression[$i];

        if (isset($braces[$char])) {
            // opening brace, pushing onto stack
            $stack[] = $state = $char;
        } else if ($state && $char == $braces[$state]) {
            // matching closing brace to current state, popping stack
            array_pop($stack);
            $state = end($stack);
        } else {
            // non-matching brace
            return false;
        }
    }

    // expecting stack to be reduced back to 0 here, otherwise fail
    return count($stack) == 0;
}

$expressions = array(")(){}","[]({})","([])","{()[]}","([)]");

var_dump(array_map('checkMatchingBraces', $expressions));

edited Aug 30 '13 at 08:52

answered Aug 30 '13 at 08:41

deceze

510,633
85
743
889

1

Try writing a parser for a simple data format like JSON or something of similar complexity; that's essentially what this does... :) – deceze Aug 30 '13 at 09:05
Would it matter if instead of: > $stack[] = $state = $char; I use: array_push($stack, $char); – Adib Aug 30 '13 at 09:09
You can leave out the `$state` variable entirely and always use `end($stack)` instead. As I commented, I just want to avoid the repeated function calls and so I'm "caching" the last stack element in `$state`. `array_push` vs. `[]` is a matter of taste, mostly. – deceze Aug 30 '13 at 09:18

score 0 · Answer 2 · edited Aug 20 '18 at 01:16

function validBraces($braces) {
    if (!is_string($braces))
        return 0;

        if (trim($braces, '(){}[]') !== '')
            return 0;

            $pile = array();

            for ($i = 0; $i < strlen($braces); $i++) {
                //App possible Closures
                if ($braces[$i] === ')' || $braces[$i] === ']' || $braces[$i] === '}') {
                    $last = array_pop($pile);
                    if ($braces[$i] === ')' && $last !== '(' || $braces[$i] === '}' && $last !== '{' || $braces[$i] === ']' && $last !== '[')
                        return 0;
                } else
                    $pile[] = $braces[$i];
            }
            return !$pile;
}

Returns 1 if true and 0 if false from Code Review

score 0 · Answer 3 · answered Nov 05 '18 at 14:39

Function #1 - if you don't like regular expressions (Demo)

function is_valid($string) {
    do {
        $string = str_replace(['()', '{}', '[]'], '', $string, $count);
    } while ($count);
    return (int)!$string;
}

Function #2 - if the idea of a recursive pattern scares you (Demo)

function is_valid($string) {
    while (($string = preg_replace('~(?:\(\)|\{}|\[])+~', '', $string, -1, $count)) && $count);
    return (int)!$string;
}

Function #3 - Casimir et Hippolyte's very clever recursive pattern (Demo)

function is_valid($string) {
    return preg_match('~(\((?1)*+\)|\[(?1)*+]|{(?1)*+})*\z~A', $string);
}

Here's some sample input and iterated function calls:

$expressions = array(")(){}", "[]({})", "([])", "{()[]}", "([)]", "{()[]}{()[]}{()[]}{()[]}{()[]}");
foreach ($expressions as $expression) {
    echo "$expression is " , is_valid($expression) , "\n";
}

Output from all:

)(){} is 0
[]({}) is 1
([]) is 1
{()[]} is 1
([)] is 0
{()[]}{()[]}{()[]}{()[]}{()[]} is 1

Matching braces puzzle

3 Answers3