Matching brackets puzzler

Matching brackets is an interesting interview puzzle, but only in so far as getting the basic approach down. Once you work out that you need to retain some form of queue of unmatched open brackets, you’re done. The rest is all syntax, minutiae, and testing.

So an interview with this question shouldn’t really be asking for working code. The basic algorithm, or approach should be enough. Really, you want to see if the person can think. If you’re looking for specific language skills, then using this kind of test is going to fail miserably, since it doesn’t represent a big enough portion of any language to be valid.

However, it looked fun, so I took this opportunity to learn some PHP. Getting a working solution took 2 hours. Most of that was discovering some weird things about PHP arrays, which was my first implementation, and then some odd things about the PHP functions.

The basic approach took about a minute of thinking. My first thought was to numerically weigh each bracket type, so ‘(’ and ‘)’ were 1, ‘{’ and ‘}’ were 2, ‘[’ and ‘]’ were 4, etc. Then simply accumalate totals moving throught the string. I quickly realized that would be easy to trick though. Plus it was over-thinking the problem.

All we really need is to track the open brackets, and if we find a closing bracket it needs to match the very last open bracket on our list. If it does match, remove the open bracket from the list.

Anyway, enough talk here’s the solution and some test cases.

Update: As usual boundary cases are the tricky ones. I now check for spurious single characters at the end of the string by making sure we have an even number of characters.

function brackets ($t) {

       $open = '({<[';
       $close = ')}>]';

       $valid = (strlen($t)%2 == 0);
       for ($i=0; ($valid && $i < strlen($t)); $i++) {
          $curr = substr($t,$i,1);
          if ( strpos($open, $curr) === false ) {
             if ( $valid = ($i!=0 && (strpos($open,substr($prev,-1)) === strpos($close,$curr)) ))
               $prev = substr($prev,0,-1);
          } else
            $prev .= $curr;
       }
       return $valid;

}

function test_brackets () {

       $arr = array (
          '(', ']', '(]', ')', ']', ')(', '][', '()(', '(p', 'p(', 'p()', '()p', '({<)>}', // FAILS
          '', '()', '[]', '[]<>', '(())', '[](<>)', '[]<>({<<()>>})', '([](<{}>))' //SUCCEED
       );

       for ($x=0; $x < count($arr); $x++) {
          $out .= $x.'] '. $arr[$x]. ': '. ( brackets($arr[$x]) ? 'valid' : 'invalid'). '<br>';
       }
       return $out;

}