Balanced Brackets

1-balanced-brackets.md

Balanced Brackets

Write a function that takes a string of brackets as the input, and determines if the order of the brackets is valid. A bracket is considered to be any one of the following characters: (, ), {, }, [, or ].

We say a sequence of brackets is valid if the following conditions are met:

• It contains no unmatched brackets.
• The subset of brackets enclosed within the confines of a matched pair of brackets is also a matched pair of brackets.

Examples:

• (){}[] is valid
• {()}{} is valid
• []{() is not valid
• [{)] is not valid

2-balanced-brackets.js

const bracketType = {
  Null: 0,
  Curly: 1,
  Square: 2,
  Paren: 3,
};

const getBracketType = (bracket) => {
  switch (bracket) {
    case '[':
    case ']':
      return bracketType.Square;
    case '{':
    case '}':
      return bracketType.Curly;
    case '(':
    case ')':
      return bracketType.Paren;
    default:
      return bracketType.Null;
  }
};

const isBalanced = (str) => {
  if (str.length <= 1) return false;

  const opening = ['[', '{', '('];
  const closing = [']', '}', ')'];
  const stack = [];
  let isValid = true;
  const chars = str.split('');

  chars.forEach((c) => {
    if (opening.includes(c)) {
      stack.push(c);
    }

    if (closing.includes(c)) {
      if (stack.length === 0) {
        isValid = false;
        return isValid;
      }

      const matchChar = stack[stack.length - 1];
      const matchType = getBracketType(matchChar);
      const charType = getBracketType(c);

      if (matchType !== charType) {
        isValid = false;
        return isValid;
      }

      stack.pop();
    }
  });

  if (stack.length > 0) {
    isValid = false;
  }
  return isValid;
};

const tests = ['(){}[]', '[{()}](){}', '[]{()', '[{)]'];
tests.map((t) => console.log(`- ${t} =`, isBalanced(t) ? 'is valid' : 'is not valid'));

3-balanced-brackets.php

<?php

interface BracketType {
    const Null      = 0;
    const Curly     = 1;
    const Square    = 2;
    const Paren     = 3;
}

function getBracketType($bracket): ?int
{
    switch ($bracket) {
        case '[':
        case ']':
            return BracketType::Square;
        case '{':
        case '}':
            return BracketType::Curly;
        case '(':
        case ')':
            return BracketType::Paren;
        default:
            return BracketType::Null;
    }
}

function isBalanced($str): bool
{
    if (!$str) {
        return false;
    }
    $opening = ['[', '{', '('];
    $closing = [']', '}', ')'];
    $stack = [];
    $isValid = true;
    $chars = str_split($str);

    foreach ($chars as $char) {
        if (!$isValid) {
            continue;
        }

        if (in_array($char, $opening)) {
            array_push($stack, $char);
        }

        if (in_array($char, $closing)) {
            if (count($stack) === 0) {
                $isValid = false;
                continue;
            }

            $matchChar = $stack[count($stack) - 1];
            $matchType = getBracketType($matchChar);
            $charType = getBracketType($char);

            if ($matchType !== $charType) {
                $isValid = false;
                continue;
            }

            array_pop($stack);
        }
    }
    if (count($stack) > 0) {
        $isValid = false;
    }
    return $isValid;
}

$tests = ['(){}[]', '[{()}](){}', '[]{()', '[{)]'];
array_map(function ($t) {
    echo "- $t = ", (boolean)isBalanced($t) ? 'is valid' : 'is not valid', PHP_EOL;
}, $tests);