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 <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.
foldM traverses the string xs, mantaining a stack of the opening brackets.
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.
The implementation uses a Maybe [] as the stack, where Maybe is employed to
represent an invalid list of brackets. The foldM function is utilized to
encapsulate the result within th Maybe monad. At the conclusion of the process,
if the result is Nothing (indicating an error), the string is not balanced.
Conversely, the string is considered balanced only if the stack is empty, which
is verified using null. The maybe function provides a default value if the
Maybe value is Nothing. Otherwise, it applies the null function to the
value inside Just and returns the result. It’s important to note that foldM
on a Maybe [] halts at the first failure (represented by Nothing), so an input
like ((]((((((( stops execution at the third character, becose there is no
opening bracket before.
This is a complete program: the interact functions reads from stdin to a
string, pass it to another function, and write to resulting string to stdout.
Here interact is composed with other functions using the . operator.
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 which may not 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()
}
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
import sys
pairs = [ ("{", "}"), ("[", "]"), ("(", ")") ]
def is_balanced(s):
stack = []
for c in s:
if stack and (stack[-1], c) in pairs:
stack.pop()
else:
stack.append(c)
return len(stack) == 0
input = [line.strip() for line in sys.stdin][1:]
output = ["YES" if is_balanced(line) else "NO" for line in input]
print("\n".join(output))
|
With reduce instead of a for loop:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
from functools import reduce
pairs = [ ("{", "}"), ("[", "]"), ("(", ")") ]
def is_balanced(s):
return (
reduce(
lambda stack, c: (
stack[:-1] # Pop
if stack and (stack[-1], c) in pairs
else stack + [c] # Push
),
s,
[],
)
== []
)
|
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');
}
|