Validating a stack sequence

This is a response to A Programming Job Interview Challenge #13 – Brackets. The solution is in PHP, which hopefully is not an issue.

#!/usr/local/bin/php
< ?php

echo intval(bracket_string_is_valid($argv[1]));

function bracket_string_is_valid($string) {
$stack = array();
$brackets = array(
'<' => '>',
'[' => ']',
'{' => '}',
'(' => ')',
);
$flipped_brackets = array_flip($brackets);

for ($x = 0; $x < strlen($string); $x++) {
$c = $string[$x];
if (in_array($c, array_keys($brackets))) {//opening bracket, push
$stack[] = $string[$x];
} else if (in_array($c, array_values($brackets))) { //closing bracket, compare
if (array_pop($stack) != $flipped_brackets[$c]) {
return false;
}
} else { //Illegal character, only (){}[]<> are allowed
return false;
}
}
return empty($stack); //if it's empty, everything has matched
}

Posted Monday, July 21st, 2008 under Programming.

One comment so far

Leave a Reply