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
}
August 5th, 2008 at 3:02 am #A PROGRAMMING JOB INTERVIEW CHALLENGE #14 - 2D GEOMETRY | Dev102.com
[...] http://www.moskalyuk.com/blog/validating-a-stack-sequence/1559 by Alex moskalyuk. [...]