Usually for problems in the code, it is interesting to put the test cases that gave error (which strings you used to test), so the others do not need to "guess" and can give more accurate answers. It’s okay that in this case it wasn’t so hard to find the problem, but here’s the tip for the next.
The logic of its function balanceada
is to add an element to the list pilha
when it is an opening character ((
, [
, {
or <
), and remove it when the corresponding lock is found.
This means that in many cases, in the middle of the run, the stack may be empty. For example, if you pass the string '())'
:
- the first
(
is added to the list
- the first
)
is found, the (
is removed from the list (so now the list is empty)
- the second
)
is found, you try to access pilha[-1]
. But since the list is empty, any attempt to access any element gives error
In the case, pilha[-1]
accesses the element at the last position of the list. But since the list is empty, there is no last element (actually, as it is empty, there is none), so the IndexError
.
There are several things that can improve the code (not just checking if the list is empty). Instead of doing if i != '(' or i != '[' ...
, you could put the valid elements in a list and test if the character is in this list, using in
:
def balanceada(string):
abertura = [ '(', '[', '{', '<' ]
fechamento = [ ')', ']', '}', '>' ]
correspondentes = { fecha: abre for abre, fecha in zip(abertura, fechamento) }
pilha = []
for i in string:
if i in abertura: # se é (, {, [ ou <
pilha.append(i)
elif i in fechamento: # se é ), }, ] ou >
if not pilha: # se a lista está vazia
return False
if correspondentes[i] == pilha[-1]:
pilha.pop()
return not bool(pilha)
I created a list with the opening characters, and another with the closing characters. I also created a dictionary containing the closing characters as key, and the value is the respective opening character. That is, the dictionary is the same as { ')': '(', ']': '[', '}': '{', '>': '<' }
: it maps each closing character to its respective opening character, so the check becomes simpler and readable than using a if
under various conditions.
To create it, I used the syntax of Dict comprehension, much more succinct and pythonic. I also used the function zip
to scroll through two lists at the same time (abertura
and fechamento
).
Then I do the for
by the characters of the string, and if the character is opening (if i in abertura
), I add it to the list.
If it is a closing character (elif i in fechamento
), first me check if the list is empty (if not pilha
). If I fall in this case (it is a closing character and the list is empty), that is to say that there is no corresponding opening character, so I can already return False
immediately, because at this point it is already clear that the expression is not well formed and it is useless to check the rest of the string.
If the list is not empty, I check if the last character in the list (pilha[-1]
) is equal to the aperture corresponding to the closing character (correspondentes[i]
).
In the end, I return True
if the list is empty, and False
otherwise. In case, I convert the list to boolean, and this conversion follows the rules of Truth Value Testing, where empty lists are considered "false" values (read more about values Truthy and falsy here ← this link is about Javascript, but the general idea is the same in Python).
Opening and closing characters could also be in strings instead of lists:
abertura = '([{<'
fechamento = ')]}>'
Since if i in abertura
and elif i in fechamento
would work in the same way, to check whether i
is one of those characters. The important thing is that the corresponding characters are in the same positions, so that the dictionary correspondentes
be mounted correctly.
Any other character that is not opening or closing is ignored (your first if
makes it seem that’s what you want).
Notice I didn’t need to put one if
specific to test whether the character is neither opening nor closing. If it is opening, it falls into the if i in abertura
, and if it’s closing, it falls on elif i in fechamento
. If it’s neither, do nothing and go to the next iteration of for
.
Testing:
print(balanceada('() ')) # True
print(balanceada('()[]{}<>')) # True
print(balanceada('(x)[y]{z}a<b>')) # True
print(balanceada('({})<[]a bc([{<< xyz >( ) > }])>')) # True
print(balanceada(' ( { [[]] <> } ) ')) # True
print(balanceada('(}')) # False
print(balanceada('())')) # False
print(balanceada('( [ )')) # False
print(balanceada('(}()')) # False