Skip to content

Instantly share code, notes, and snippets.

@belushkin
Last active September 26, 2018 16:24
Show Gist options
  • Save belushkin/07cabb5b56320e0e687afce64c643b9c to your computer and use it in GitHub Desktop.
Save belushkin/07cabb5b56320e0e687afce64c643b9c to your computer and use it in GitHub Desktop.
Balanced unbalanced string
<?php
// (if (zero? x) max (/ 1 x))
function balance($str)
{
function loop($str, $acc)
{
if (empty($str)) {
return $acc == 0;
}
$h = head($str);
if ($h == "(") {
$n = $acc + 1;
} elseif($h == ")") {
$n = $acc - 1;
} else {
$n = $acc;
}
if ($n >= 0) {
return loop(tail($str), $n);
}
return false;
}
return loop($str, 0);
}
function head($str)
{
return $str[0];
}
function tail($str)
{
return substr($str, 1);
}
$balance = balance("(if (zero? x) max (/ 1 x))");
if ($balance) {
echo "balanced\n";
} else {
echo "unbalanced\n";
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment