balanced-braces.php

<?php

class BracesToken {
  private $ch = null;
  // store char index for simplicity
  private $index = null;
  // keys are opening braces
  // values are theirs closing brases respectively
  private static $pairs = array('[' => ']', '(' => ')', '{' => '}');

  function __construct($ch, $index) {
    $this->ch = $ch;
    $this->index = $index;
    if (!$this->getPair()) {
      throw new Exception('wrong input char');
    }
  }

  function getIndex() {
    return $this->index;
  }

  function getPair() {
    if (isset(self::$pairs[$this->ch])) {
      return self::$pairs[$this->ch];
    }
    elseif ($idx = array_search($this->ch, self::$pairs)) {
      return $idx;
    }
  }

  function isPair(BracesToken $token) {
    return $token->getPair() == $this->ch;
  }

  function isOpening() {
    return isset(self::$pairs[$this->ch]);
  }

  function __toString() {
    return "$this->index:$this->ch";
  }
}

class BracesChecker {
  function check($input) {
    $chain = array_map(function($ch, $idx) {
      return new BracesToken($ch, $idx);
    }, str_split($input), range(0, strlen($input) - 1));

    list($stack, $tail) = $this->balance(array(), $chain);

    if (count($stack) == 0 && count($tail) == 0) {
      return -1;
    }

    $firstUnbalanced = count($stack) ? $stack[0]->getIndex() : $tail[0]->getIndex();
    while (count($stack) > 0 && count($tail) > 0) {
      list($stack1, $tail1) = $this->balance($stack, $tail, true);

      if (count($stack1) == 0) {
        return end($stack)->getIndex() + 1;
      }
      else {
        // try to remove one element from stack to balance the rest
        array_pop($stack);
      }
    }

    return $firstUnbalanced;
  }

  /**
   * @param array $stack - stack to keep opening braces,
   * @param array $tail - braces chain to to balance
   * @param bool $tryBalance - if true - drop unbalanced braces from tail and do not accept new opening braces
   * @return array
   *    returns unbalances opening braces ($stack) and tail (if we found unexpected token)
   */
  function balance($stack, $tail, $tryBalance = false) {
    foreach ($tail as $idx => $next) {
      $current = end($stack);
      if ($this->expectedToken($current, $next, $tryBalance)) {
        if ($next->isOpening()) {
          array_push($stack, $next);
        }
        else {
          // do not store balanced sub-trees
          array_pop($stack);
        }
      }
      elseif ($tryBalance) {
        continue;
      }
      else {
        // failed to balance, return stack + tail
        return array($stack, array_slice($tail, $idx));
      }

    }
    return array($stack, array());
  }

  function expectedToken($current, BracesToken $next, $tryBalance = false) {
    return (!$tryBalance && $next->isOpening() || $current && $next->isPair($current));
  }
}

$checker = new BracesChecker();
$input = fgets(STDIN);
print $checker->check(trim($input));
exit();
//
//$tests = array(
//  "{}[]()" => -1,
//  "{[(]}" => 2,
//  "[{}{}]()" => -1,
//  "[{}{}](}" => 6,
//  "[{}{}]}" => 6,
//  "{[(" => 0,
//  "{[]}({" => 4,
//  "(}{)" => 1,
//  "[{([)(}]])}]" => 4,
//  "[{([)(}]])}" => 3,
//);
//
//foreach ($tests as $input => $res) {
//  $res1 = $checker->check($input);
//  $failed = $res != $res1 ? "failed!" : '';
//
//  echo "\n\n== check $input => expected:$res, found:$res1. $failed\n";
//}
//