Balanced Brackets · Coding Gym

Solutions

Stack

This is a classical problem which requires a stack.

Possible C++ Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


#include <stack>
#include <map>
#include <iostream>
using namespace std;

static const map<char, char> closedParen {
    {')', '('}, {']', '[',}, {'}', '{'}
};

int main()
{
    int N; cin >> N;
    string line;
    while (N--)
    {
        stack<char> paren;
        bool error = false;
        cin >> line;
        for (auto c : line)
        {
            if (c == '(' || c == '[' || c == '{')
                paren.push(c);
            else // is a closing bracket
            {
                if (paren.empty() || (paren.top() != closedParen.at(c)))
                {
                    error = true;
                    break;
                }
                paren.pop();
            }
        }
        error |= !paren.empty();
        cout << (error ? "NO" : "YES") << endl;
    }
}

Here is a Javascript alternative by Lucio Grenzi:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    const open = '{[('
    const lookup = {
        '}': '{',
        ']': '[',
        ')': '('
    }

    input_stdin.split('\n').slice(1).forEach(s => {
        var stack = []

        for(var i = 0; i < s.length; i++) {
            const c = s[i]

            if(open.includes(c)) {
                stack.unshift(c)
            } else if(lookup[c] !== stack.shift()) {
                return console.log('NO')
            }
        }

        console.log(stack.length ? 'NO' : 'YES')
    })
})

A functional approach in Haskell by Alessandro Pezzato

Uses a Maybe [] as the stack. The Maybe is used to express an invalid list of brackets. foldM is used to encapsulate the result in the Maybe monad. At the end, if the result is Nothing (an error), the string is not balanced, otherwise it’s balanced only if empty (checked by null). The maybe function returns the default value if the Maybe value is Nothing. Otherwise, it applies the function null to the value inside the Just and returns the result. Note that foldM on a Maybe [] stops at ther first failure (expressed by Nothing), so an input like ((]((((((( stops the execution at the ], i.e. the first non matching bracket.

The interact function just read all from stdin, pass it to an anonymous function that parse the input line by line (lines), ignore the first line (tail), pass each line to isBalanced and write in back.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


import Control.Monad (foldM)

isBalanced :: String -> Bool
isBalanced xs = maybe False null $ foldM go [] xs
  where
    go s v
      | v `elem` "{[(" = Just (v : s)
      | null s = Nothing
      | match (head s) v = Just (tail s)
      | otherwise = Nothing
    match '{' '}' = True
    match '[' ']' = True
    match '(' ')' = True
    match _ _ = False

yesNo True = "YES"
yesNo False = "NO"

main = interact . unlines . fmap (yesNo . isBalanced) . tail . lines

In Rust we can use a mutable Vec as the stack and pattern match brackets. stack.last() return an Option<char> (similar to Haskell’s Maybe) to work safely on a value that cannot exist.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


fn is_balanced(string: &str) -> bool {
    fn brackets_match(l: char, r: char) -> bool {
        match (l, r) {
            ('(', ')') => true,
            ('[', ']') => true,
            ('{', '}') => true,
            _ => false,
        }
    }

    let mut stack = Vec::new();

    for r in string.chars() {
        if stack.last().map_or(false, |&l| brackets_match(l, r)) {
            stack.pop();
        } else {
            stack.push(r);
        }
    }

    stack.is_empty()
}

The next solution always pop the last element when a closing bracket is found, exiting as soon as a non matching is found.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


fn is_balanced(string: &str) -> bool {
    let mut stack = Vec::new();

    for r in string.chars() {
        match r {
            '(' | '[' | '{' => stack.push(r),
            ')' | ']' | '}' => match (stack.pop(), r) {
                (Some('('), ')') => {}
                (Some('['), ']') => {}
                (Some('{'), '}') => {}
                (_, ')') => return false,
                (_, ']') => return false,
                (_, '}') => return false,
                _ => {}
            },
            _ => {}
        }
    }

    stack.is_empty()
}

Replace regular expressions

We can replace adjacent matching brackets until there are no other replacement to be done. If the resulting string is empty, the result is YES, otherwise it is NO.

We can express this algorithm with a loop: (solution by Davide Trevisan)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


function isBalanced(s) {
  var oldString = s
  while (true) {
    var ss = oldString.replace(/\{\}/g, '').replace(/\[\]/g, '').replace(/\(\)/g, '');
    if (oldString === ss) {
      if (ss === '')
        return 'YES'
      else
        return 'NO'
    } else {
      oldString = ss;
    }
  }
}

or with a more concise recursion:

1
2
3
4


function isBalanced(s) {
  const ss = s.replace(/\{\}/g, '').replace(/\[\]/g, '').replace(/\(\)/g, '');
  return s !== ss ? isBalanced(ss) : (ss === '' ? 'YES' : 'NO');
}

stack