Skip to content

Instantly share code, notes, and snippets.

@nnnikolay
Last active December 14, 2016 16:38
Show Gist options
  • Save nnnikolay/e2bc3db8f1b0874ecc9c to your computer and use it in GitHub Desktop.
Save nnnikolay/e2bc3db8f1b0874ecc9c to your computer and use it in GitHub Desktop.
Balanced braces
<?php
define('OPENED_BRACE', '{');
define('CLOSED_BRACE', '}');
define('OPENED_PARENTHESIS', '(');
define('CLOSED_PARENTHESIS', ')');
define('OPENED_BRACKET', '[');
define('CLOSED_BRACKET', ']');
$values = [
'() [] () ([]()[])',
'( (] ([)]',
'{}[]()',
'{{}]}',
'{[}',
'[}]'
];
print_r(braces($values));
function braces($values)
{
$result = [];
foreach($values as $value) {
$result[] = is_balanced($value);
}
return $result;
}
function is_balanced($string)
{
$stack = [];
$allowed_order = [
CLOSED_BRACKET => OPENED_BRACKET,
CLOSED_PARENTHESIS => OPENED_PARENTHESIS,
CLOSED_BRACE => OPENED_BRACE
];
$allowed_closed_braces = array_keys($allowed_order);
$allowed_opened_braces = $allowed_order;
for($i = 0; $i < strlen($string); $i++) {
$char = $string[$i];
// add opening brace
if(empty($stack) || in_array($char, $allowed_opened_braces)) {
$stack[] = $char;
continue;
}
// validate that only proper closing brace are allowed
if(in_array($char, $allowed_closed_braces)) {
$last_elemnt_in_stack = $stack[count($stack) - 1];
if($last_elemnt_in_stack !== $allowed_order[$char]) {
return "NO";
} else {
array_pop($stack);
}
}
}
return "YES";
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment