Created
May 5, 2018 06:30
-
-
Save jsgoller1/cec9e185faf9a6355e131b92bc52c092 to your computer and use it in GitHub Desktop.
HackerRank issue or just me?
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
""" | |
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