Skip to content

Instantly share code, notes, and snippets.

@bmwant
Created May 8, 2019 12:09
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bmwant/6fd60220d1c388f58c2aba9efcf115db to your computer and use it in GitHub Desktop.
Save bmwant/6fd60220d1c388f58c2aba9efcf115db to your computer and use it in GitHub Desktop.
Balance parentheses
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