I was recently trying to solve a challenge on Hackerrank which asked us to figure out whether a string containing brackets (e.g. {}, (), and [] ) was balanced or not (source: https://www.hackerrank.com/challenges/balanced-brackets). I wanted to solve this using the following approach that also integrated the initial format Hackerrank provided:
import sys
def isBalanced(s):
#insert code here
if __name__ == "__main__":
t = int(raw_input().strip())
for a0 in xrange(t):
s = raw_input().strip()
result = isBalanced(s)
print result
I should also note that site has configured the following as being the standard input in order to test the functionality of the code:
3
{[()]}
{[(])}
{{[[(())]]}}
In order to get the following output:
YES
NO
YES
However, I didn't understand how to approach this code, chiefly because I did not understand why Hackerrank used the if __name__ == "__main__": clause, as I thought that this clause was only used if someone wanted their module to be executed directly rather than executed through being imported in another script (source: What does if __name__ == "__main__": do?). I also did not understand the for loop containing for a0 in xrange(t): since a0 is not used within the for loop for anything, so I'm really unsure how the standard input would be processed.
So I ended up looking up the solution on the discussion page, and here it is below:
lefts = '{[('
rights = '}])'
closes = { a:b for a,b in zip(rights,lefts)}
def valid(s):
stack = []
for c in s:
if c in lefts:
stack.append(c)
elif c in rights:
if not stack or stack.pop() != closes[c]:
return False
return not stack # stack must be empty at the end
t = int(raw_input().strip())
for a0 in xrange(t):
s = raw_input().strip()
if valid(s):
print 'YES'
else:
print 'NO'
This code also confuses me, as the writer claimed to utilize a data structure known as a "stack" (although it seems to be just a Python list to me). And although the writer removed the if __name__ == "__main__": statement, they retained the for a0 in xrange(t):, which I'm not sure how it processes the standard input's integer and corresponding strings.
Furthermore, although the isBalanced function confuses me because it returns not stack. In a hash comment on the return statement of the function, the writer also states the # stack must be empty at the end. What does that mean? And how could this list be empty if, during the clause if c in lefts:, the stack is appended with the character of the string that is being iterated in the for-loop. So why would the function return not stack? Wouldn't it be consistent to return True so that the function would act as a Boolean tester (i.e. would return true if a certain object adhered to certain criteria, and false if the the object did not)?
I am still relatively new to coding so there are a lot of principles I am not familiar with. Can anyone illuminate as to how this would work?
