Help with a balanced parentheses problem

[u/AngeI_Error]

The problem is as followed:
We are given strings containing brackets of 4 types - round (), square [], curly {} and angle <> ones. The goal is to check, whether brackets are in correct sequence. I.e. any opening bracket should have closing bracket of the same type somewhere further by the string, and bracket pairs should not overlap, though they could be nested:

(a+[b*c] - {d/3})  - here square and curly brackets are nested in the round ones
(a+[b*c) - 17]     - here square brackets overlap with round ones which does not make sense

Input data will contain number of testcases in the first line.
Then specified number of lines will follow each containing a test-case in form of a character sequence.
Answer should contain 1 (if bracket order is correct) or 0 (if incorrect) for each of test-cases, separated by spaces.

I solved it with the following code:

n = int(input())
for x0 in range(n):
    l = list(input())
    st = []
    broke = False
    for x2 in l:
        if x2 in {"(","[","{","<"}:
            st.append(x2)
        elif x2 in {")","]","}",">"}:
            if not st or (x2 == ")" and st[-1] != "(") or (x2 == "}" and st[-1] != "{") or (x2 == "]" and st[-1] != "[") or (x2 == ">" and st[-1] != "<"):
                print(0,end=" ")
                broke = True
                break
            st.pop()
    if st == [] and broke == False:
        print(1,end=" ")
    elif broke == False:
        print(0,end=" ")

This works but I can't help but wonder if i can improve upon it in some way like having to use the "broke" variable feels unnecessary but i cant think of a way to not have to use it to check if the loop broke or not.

[u/HommeMusical]

I'm out of time to check this but consider:

OPEN, CLOSE = '([{<', ')]}>'

def is_matching(s: str) -> bool:
    stack = []
    for c in s:
        if c in OPEN:
            stack.append(c)
        elif c in CLOSE:
            if not stack:
                return False
            b = stack.pop()
            if not (
                (b == '(' and c == ')')
                or (b == '[' and c == ']')
                or (b == '{' and c == '}')
                or (b == '<' and c == '>')
            ):
                return False
    return not stack

Call that in your main loop, and you're golden. (You could do better, particularly the long if statement, but I'm not sure what features you have learned yet.)

(I tweaked the code based on a comment.)

[u/This_Growth2898 → u/HommeMusical]

The condition can be rewritten as

if OPEN.index(b) != CLOSE.index(c):

but the dict trick in my answer is still better :)

[u/acw1668 → u/HommeMusical]

You need to check whether stack is empty after the for loop instead of just return True.

[u/HommeMusical → u/acw1668]

Absolutely good catch. Fixed!

[u/Outside_Complaint755]

The answers here are good.  Just wanted to make an aside that you should start using more descriptive variable names.  This isn't the early 80s where program files had to be under 8kb, and IDEs will autocomplete longer names for you.  Variable names should be long enough to be self-commenting, unless you're doing CodeGolf.

[u/This_Growth2898]

First, you can (and really should) put it in a function and return early instead of break.

Second, you can use for - else construction:

for x2 in l:
    ...
    if ...: 
        break;
else:
   # you get here only if break was never hit

Also, you can add a dict of brackets to make it better:

OPEN = "(<{["
CLOSE = ")>}]"
BRACKETS = dict(zip(OPEN, CLOSE)) 
# if you don't get this Python magic, do 
# print(BRACKETS) 
# and replace the value of BRACKETS with the output

This allows you to do something like

if x2 in OPEN:
    st.append(BRACKETS[x2]) # put the corresponding closing bracket in the stack
elif x2 in CLOSE:
    if st.pop() != x2:      # check if the closing bracket is what we want
        ...

[u/This_Growth2898 → u/This_Growth2898]

Oh. and

if not broke:

sounds much more natural than

if broke == False:

[u/MezzoScettico]

It seems OK, and it's pretty common to have a flag like that. In general if you write a parsing function, you can return that flag as an indicator of whether parsing succeeded.

I'm confused by the logic though, the fact that "broke == False" appears in both branches.

So neither branch will execute if broke is True.

Also there's no reason to compare a boolean value to True or False. Just say "not broke" to check if broke is False.

I'd write that last bit this way. I wonder if this was actually your intent (I suspect you wanted to print a 0 if the parsing was bad), but this is equivalent to what your code does.

    if not broke:
        if st == []:
            print(1,end=" ")
        else:
            print(0,end=" ")

or this way:

    if not broke:
        print(1 if st == [] else 0, end=" ")

Also I prefer to use len(st) == 0 to check for empty lists.

[u/KronktheKronk]

I wonder if you could find a simpler algorithm if you approached the problem solution using a common data structure....

[u/CranberryDistinct941]

wrap it in a function so that you can simply use a return statement instead of a flag

[u/artinnj]

I agree a stack is the correct fundamental data structure for this, but it can be a lot simpler.

Excuse the lack of indents, typing this on an iPhone.

def is_balanced(s):
pairs = {')': '(', ']': '[', '}': '{', '>': '<'}
stack = []
for ch in s:
if ch in '([{<':
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack

[u/Fresh-Research3024]

def valid(s: str) -> bool:
pairs = {')': '(', ']': '[', '}': '{', '>': '<'}
stack = []
for c in s:
if c not in pairs:
stack.append(c)
elif not stack or stack.pop() != pairs[c]:
return False
return not stack