Balance braces method

Question

This is a continuation of this question, at least the first part of that question. I want to check if everything in the new code is right or if there are other way to make it better.

Exercise

The validBraces method takes a string of braces as a single parameter and determines if the order of the braces is valid. All input strings will only consist of open curly braces {, closed curly braces }, open parentheses (, closed parentheses ), and open brackets [ and closed brackets ].

• A string of braces is considered valid if all open braces are matched with their corresponding closed brace. For example: (){}[] and ([{}]) would be considered valid, while (}, [(]), and [({})](] would be considered invalid.
• An empty string is considered valid.
• A non-string input is considered an invalid input. The method should throw an InvalidArgumentException in this case.

class StringUtil {

  public function validBraces($braces) {
    if ($braces === "") {
      return true;
    } elseif (!is_string($braces)) {
      throw new InvalidArgumentException("Not a string");
    }

    $balance = array();

    for ($i = 0; $i < strlen($braces); $i++) {
      //allowed chars  (){}[]
      if (!($braces[$i] === "(" || $braces[$i] === ")" 
           || $braces[$i] === "{" || $braces[$i] === "}" 
           || $braces[$i] === "[" || $braces[$i] === "]")) {
        throw new InvalidArgumentException("Invalid string");
      } elseif ($braces[$i] === "(" || $braces[$i] === "{" || $braces[$i] === "[") {
        array_push($balance, $braces[$i]);
      } elseif ($braces[$i] === ")") {
        if (array_pop($balance) !== "(") {
          return false;
        }
      } elseif ($braces[$i] === "}") {
        if (array_pop($balance) !== "{") {
          return false;
        }
      } elseif ($braces[$i] === "]") {
        if (array_pop($balance) !== "[") {
          return false;
        }
      }
    }

    if (count($balance) == 0) {
      return true;
    }

    return false;
  }
}

Answer 1

public function validBraces($braces) {

I'd call this isValidBraces instead to show that it returns a Boolean value. This also makes it read a little better in normal usage.

if ($braces === "") {

The difference between "" and '' is that the double quoted string allows variable interpolation. Since you are not using variable interpolation, consider

if ( '' === $braces ) {

The single quoted string will also be slightly quicker to interpret, although I don't know that the difference would matter in this case.

I also changed the order. It's not uncommon to see the constant on the left in C-based languages. This is because '' = $braces would give a compiler error while $braces = '' will happily evaluate as false and continue.

Incidentally, you don't need this statement, as the later for loop and count check will handle this case for you. There's an argument that the code is a little cleaner without this check. It certainly would be a little shorter.

$balance = array();

I might call this $open_braces. It doesn't balance anything. It's a stack of all the currently open braces, so call it that.

for ($i = 0; $i < strlen($braces); $i++) {

As a general rule, you want to avoid calling a function on every loop iteration which always returns the same value.

for ($i = 0, $n = strlen($braces); $i < $n; $i++) {

That way you only do the strlen call once at the initialization of the loop. Each iteration can do the simpler check instead.

  if (!($braces[$i] === "(" || $braces[$i] === ")" 
       || $braces[$i] === "{" || $braces[$i] === "}" 
       || $braces[$i] === "[" || $braces[$i] === "]")) {

It's possible to write the if more simply by first defining a constant:

private $closing_match_of = array( '(' => ')', '{' => '}', '[' => ']' );

Then set a variable in the function before the loop starts:

$opening_match_of = array_flip($this->closing_match_of);

The array_flip will reverse the arrows from the way that they are in CLOSING_MATCH_OF. So where you had '{' => '}', you will now have '}' => '{'. Using the array_flip ensures that you will have parallel matches in both. You could declare a second constant, but then that would be fragile in the face of changes. This way you can make changes in a single place.

Then replace the if as follows:

  if ( isset($this->closing_match_of[$braces[$i]]) ) {
    $open_braces[] = $braces[$i];
  } elseif ( isset($opening_match_of[$braces[$i]]) ) {
    if ( array_pop($open_braces) !== $opening_match_of[$braces[$i]] ) {
      return false;
    }
  } else {
    throw new InvalidArgumentException('Invalid string');
  }

This checks if the character at position $i in the $braces string has a closing match (i.e. is a key in the $this->closing_match_of array). If so, then you know that it is an opening brace and add it to the list of things that you need to match. If not, it checks if $braces[$i] has an opening match (i.e. if it is a key in the $opening_match_of array). If so, then it checks to see if it matches the most recent unmatched open brace. If not, then it returns false to indicate that the string does not consist of matching braces.

The final case is if the character has no closing match nor opening match defined in the arrays. In that case, it's not a brace. Since the string is supposed to consist entirely of braces, it throws the exception. We don't have to check anything in this case because we already did the checks earlier in the if and elseif clauses.

If you are only adding one element to the end of an array, the []= operator is more efficient than an array_push.

I changed the order of the checks to avoid repeating them. The other way you did two or three checks on a valid case and two on an invalid case. This way, you do one or two on a valid case and two on an invalid case. Hopefully the valid cases are more common.

Note that I haven't tried to run or test this code.

Answer 2

Your code works well for all the cases. After many tries and tests, I obtain two different ways to write the function.

The first comes from your approach with several changes. I have, in particular, removed the test for foreign characters from the main loop:

public function validBracesEmi($braces) {
    if (!is_string($braces))
        throw new InvalidArgumentException('Not a string');

    if (trim($braces, '(){}[]') !== '')
        throw new InvalidArgumentException('Invalid string'); 

    $stack = array();

    for ($i = 0; $i < strlen($braces); $i++) {
        if ($braces[$i] === ')' || $braces[$i] === ']' || $braces[$i] === '}') {
            $last = array_pop($stack);
            if ($braces[$i] === ')' && $last !== '(' || $braces[$i] === '}' && $last !== '{' || $braces[$i] === ']' && $last !== '[')
                return false;
        } else
            $stack[] = $braces[$i];
    }
    return !$stack;
}

The second approach is totally different and uses a regex approach. If it uses more memory (~3X) and is a little slower when you try it only one time with a little string (less than 10 characters), it becomes faster when you use it several times (whatever the size of the string) and is more efficient than the other way with long strings whatever the number of attempts. In other words, you need to pay the cost of the regex engine, but only one time.

const BALANCED_BRACES_PATTERN = '~(\((?1)*+\)|\[(?1)*+]|{(?1)*+})*+\z~A';

public function validBracesCaz($str) {
    if (!is_string($str))
        throw new InvalidArgumentException('Not a string');

    if (trim($str, '()[]{}') !== '') 
        throw new InvalidArgumentException('Invalid string');

    if (preg_match(self::BALANCED_BRACES_PATTERN, $str))
        return true;

    $pcre_error = preg_last_error();

    if ($pcre_error === PREG_NO_ERROR)
        return false;

    if ($pcre_error === PREG_BACKTRACK_LIMIT_ERROR) 
        throw new Exception('backtracking limit exhausted.');

    if ($pcre_error === PREG_RECURSION_LIMIT_ERROR)
        throw new Exception('recursion limit exhausted.');
}