Python: Indexerror: list index out of range

Asked

Viewed 629 times

1

Does anyone know why you’re returning "list index out of range"?

def balanceada(string):
    pilha = []
    for i in string:
        if i != '(' or i != '[' or i != '{' or i != '<' or i != ')' or i != ']' or i != '}' or i != '>':
            pass
        if i == '(' or i == '[' or i == '{' or i == "<":
            pilha.append(i)
        else:
            if (i == ")" and pilha[-1] == "(") or (i == "]" and pilha[-1] == "[") or (i == "}" and pilha[-1] == "{") or (i == ">" and pilha[-1] == "<"):
                pilha.pop()
            else:
                return False
    if len(pilha) == 0:
        return True
    else:
        return False

3 answers

3

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

1

Change the function’s Return by hkotsubo by the following:

    return ('%s -> \'%s\'' % (not bool(pilha), string))

so you can see the string that was passed to the function.

1

The problem is on line 9 in pilha[-1]. At some point in the implementation of the programme, the list pilha is empty, that is, you are trying to access an item that does not exist, generating the IndexError.

Try to improve your conditionals so that the list pilha do not stay made when arriving at the parole line 9 or else add to your condition len(pilha) > 0. Example:

def balanceada(string):
    pilha = []
    for i in string:
        if i != '(' or i != '[' or i != '{' or i != '<' or i != ')' or i != ']' or i != '}' or i != '>':
            pass
        if i == '(' or i == '[' or i == '{' or i == "<":
            pilha.append(i)
        else:
            if len(pilha) > 0 and (i == ")" and pilha[-1] == "(") or (i == "]" and pilha[-1] == "[") or (i == "}" and pilha[-1] == "{") or (i == ">" and pilha[-1] == "<"):
                pilha.pop()
            else:
                return False
    if len(pilha) == 0:
        return True
    else:
        return False

Browser other questions tagged

You are not signed in. Login or sign up in order to post.