Checking balanced brackets using stacks
Hi, today's problem is a relatively common one in technical interviews, here it is from Daily Coding Problem:
Here is the approach:
- First have a hash table which you can use to (quickly) map an open bracket to a closed bracket. You can also use it as an open bracket checker
- Then use a standard stack. Push open brackets. Pop closed ones, check for matches.
- Stack should be empty at the end
That's it, code is on Github https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem10112018.cs and below, thanks, Marcelo
This problem was asked by Facebook.
Given a string of round, curly, and square open and closing brackets, return whether the brackets are balanced (well-formed).
For example, given the string "([])[]({})", you should return true.
Given the string "([)]" or "((()", you should return false.
- First have a hash table which you can use to (quickly) map an open bracket to a closed bracket. You can also use it as an open bracket checker
- Then use a standard stack. Push open brackets. Pop closed ones, check for matches.
- Stack should be empty at the end
That's it, code is on Github https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem10112018.cs and below, thanks, Marcelo
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;
namespace DailyCodingProblem
{
class DailyCodingProblem10112018
{
public bool BracketsBalanced(string str)
{
if (String.IsNullOrEmpty(str)) return true;
string b = "(){}[]";
Hashtable brackets = new Hashtable();
for (int i = 0; i < b.Length; i += 2) brackets.Add(b[i], b[i + 1]);
Stack stack = new Stack();
for (int i = 0; i < str.Length; i++)
{
if (brackets.ContainsKey(str[i])) stack.Push(str[i]);
else
{
if (stack.Count == 0) return false;
char c = stack.Pop();
if (!brackets.ContainsKey(c) || (char)brackets[c] != str[i]) return false;
}
}
return stack.Count() == 0;
}
}
}
Very nice! This problem is also available on leetcode - https://leetcode.com/problems/valid-parentheses. Smart compilers are actually able to generate more efficient lookup tables for switches and in some languages the implementation is fairly concise. For example my Rust implementation defines a match_of lookup function that is based on pattern matching (fancy switch):
ReplyDeleteimpl Solution {
pub fn is_valid(s: String) -> bool {
let mut stack = Vec::new();
let match_of = |c: char| -> char {
match c {
')' => '(',
'}' => '{',
']' => '[',
_ => panic!("Invalid closing bracket"),
}
};
for ch in s.chars() {
match ch {
'(' | '{' | '[' => stack.push(ch),
closing => {
if let Some(closing_bracket) = stack.pop() {
if closing_bracket != match_of(closing) {
return false;
}
} else {
return false;
}
}
}
}
stack.is_empty()
}
}
https://gist.github.com/ttsugriy/3dc568c9e55b90233849090707f065b3
Cheers,
Taras