Skip to content

Instantly share code, notes, and snippets.

@jsgoller1
Created May 5, 2018 06:30
Show Gist options
  • Save jsgoller1/cec9e185faf9a6355e131b92bc52c092 to your computer and use it in GitHub Desktop.
Save jsgoller1/cec9e185faf9a6355e131b92bc52c092 to your computer and use it in GitHub Desktop.
HackerRank issue or just me?
"""
Go to the following link and paste the below code: https://www.hackerrank.com/challenges/ctci-balanced-brackets/problem
Issue: An empty deque (or list) "magically" has uninserted values present when initialized.
Steps to reproduce:
1) Run this code to see it passes the test cases.
2) Comment out the __init__() method in the stack, and replace "contents = None" with "contents = deque()" or "contents = []"
3) Run to observe it fails the test cases.
4) Beneath "s = stack()" in is_matched(), create a new line and put "s.dump()" on it.
5) Re-run the sample test cases. Observe that the third case prints "['{', '[']"
Expected output:
On step 5, the third test case should print "[]"
"""
from collections import *
openers = ['(','[','{']
closers = [')',']', '}']
parens = ['(', ')']
squares = ['[', ']']
curlys = ['{', '}']
class stack:
contents = None
def __init__(self):
self.contents = deque()
def dump(self):
print(self.contents)
def size(self):
return len(self.contents)
def push(self, val):
self.contents.append(val)
def pop(self):
if len(self.contents) == 0:
return ''
return self.contents.pop()
# test_type(): determine if two chars are same type of brace
def test_type(a, b):
are_parens = (a in parens) and (b in parens)
are_curlys = (a in curlys) and (b in curlys)
are_squares = (a in squares) and (b in squares)
return (are_parens or are_curlys or are_squares)
# is_matched(): determine if a string is a balanced bracket string
def is_matched(expression):
s = stack()
for char in expression:
if char in openers:
s.push(char)
else:
recent_opener = s.pop()
if not test_type(recent_opener, char):
return False
# Catch unmatched left braces
if (s.size() > 0):
return False
else:
return True
t = int(input().strip())
for a0 in range(t):
expression = input().strip()
if is_matched(expression) == True:
print("YES")
else:
print("NO")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment