Created
May 8, 2019 12:09
-
-
Save bmwant/6fd60220d1c388f58c2aba9efcf115db to your computer and use it in GitHub Desktop.
Balance parentheses
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
OPEN_BRACKETS = '[{(' | |
CLOSING_BRACKETS = ']})' | |
def is_matching(open_bracket: str, close_bracket: str) -> bool: | |
return OPEN_BRACKETS.index(open_bracket) == \ | |
CLOSING_BRACKETS.index(close_bracket) | |
def is_balanced(input_string: str) -> bool: | |
# String should have at least one bracket | |
if not any([bracket in input_string for bracket in OPEN_BRACKETS]): | |
return False | |
stack = [] | |
for char in input_string: | |
if char in OPEN_BRACKETS: | |
stack.append(char) | |
elif char in CLOSING_BRACKETS: | |
matching_open = stack.pop() if stack else '' | |
if not is_matching(matching_open, char): | |
return False | |
# Stack should be empty if all brackets matched | |
return not stack | |
class Solution(object): | |
def __call__(self, *args, **kwargs): | |
# Positive cases | |
assert is_balanced('(a[0]+b[2c[6]]) {24 + 53}') is True | |
assert is_balanced('f(e(d))') is True | |
assert is_balanced('[()]{}([])') is True | |
# Negative cases | |
assert is_balanced('((b)') is False | |
assert is_balanced('(c]') is False | |
assert is_balanced('{(a[])') is False | |
assert is_balanced('([)]') is False | |
assert is_balanced(')(') is False | |
# Corner cases | |
assert is_balanced('') is False | |
assert is_balanced('without brackets') is False | |
s = Solution() | |
s() # check |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment