# Balanced Brackets

See the original problem on HackerRank.

## 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 #include #include using namespace std; static const map closedParen { {')', '('}, {']', '[',}, {'}', '{'} }; int main() { int N; cin >> N; string line; while (N--) { stack 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'); } 
We've worked on this challenge in these gyms: modena  padua  milan  turin