1

Alguém sabe por que está devolvendo "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 Respostas 3

3

Geralmente para problemas no código, é interessante você colocar os casos de teste que deram erro (quais strings você usou para testar), assim os demais não precisam "adivinhar" e podem dar respostas mais precisas. Tudo bem que neste caso não foi tão complicado achar o problema, mas fica a dica para as próximas.


A lógica da sua função balanceada é adicionar um elemento na lista pilha quando ele é um caractere de abertura ((, [, { ou <), e removê-lo quando o fechamento correspondente é encontrado.

Isso quer dizer que em muitos casos, no meio da execução, a pilha pode estar vazia. Por exemplo, se você passar a string '())':

  • o primeiro ( é adicionado na lista
  • o primeiro ) é encontrado, o ( é removido da lista (então agora a lista está vazia)
  • o segundo ) é encontrado, você tenta acessar pilha[-1]. Mas como a lista está vazia, qualquer tentativa de acessar qualquer elemento dá erro

No caso, pilha[-1] acessa o elemento na última posição da lista. Mas como a lista está vazia, não existe o último elemento (na verdade, como ela está vazia, não existe nenhum), por isso ocorre o IndexError.


Tem várias coisas que podem melhorar no código (não apenas a verificação se a lista está vazia). Em vez de fazer if i != '(' or i != '[' ..., você poderia colocar os elementos válidos em uma lista e testar se o caractere está nesta lista, usando 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)

Eu criei uma lista com os caracteres de abertura, e outra com os caracteres de fechamento. Também criei um dicionário contendo os caracteres de fechamento como chave, e o valor é o respectivo caractere de abertura. Ou seja, o dicionário é o mesmo que { ')': '(', ']': '[', '}': '{', '>': '<' }: ele mapeia cada caractere de fechamento para o seu respectivo caractere de abertura, assim a verificação fica mais simples e legível do usar um if com várias condições.

Para criá-lo, usei a sintaxe de dict comprehension, bem mais sucinta e pythônica. Também usei a função zip para percorrer duas listas ao mesmo tempo (abertura e fechamento).

Em seguida, eu faço o for pelos caracteres da string, e caso o caractere seja de abertura (if i in abertura), eu adiciono-o na lista.

Se for um caractere de fechamento (elif i in fechamento), primeiro eu verifico se a lista está vazia (if not pilha). Se eu caio neste caso (é um caractere de fechamento e a lista está vazia), quer dizer que não existe o caractere de abertura correspondente, então eu já posso retornar False imediatamente, pois neste ponto já está claro que a expressão não está bem formada e nem adianta verificar o restante da string.

Se a lista não estiver vazia, eu verifico se o último caractere da lista (pilha[-1]) é igual à abertura correspondente ao caractere de fechamento (correspondentes[i]).

No final, eu retorno True se a lista estiver vazia, e False caso contrário. No caso, eu converto a lista para booleano, e esta conversão segue as regras do Truth Value Testing, no qual listas vazias são consideradas valores "falsos" (leia mais sobre valores truthy e falsy aqui este link é sobre JavaScript, mas a ideia geral é a mesma no Python).


Os caracteres de abertura e fechamento também poderiam estar em strings em vez de listas:

abertura = '([{<'
fechamento = ')]}>'

Já que if i in abertura e elif i in fechamento funcionariam da mesma maneira, para verificar se i é um desses caracteres. O importante é que os caracteres correspondentes estejam nas mesmas posições, para que o dicionário correspondentes seja montado corretamente.


Qualquer outro caractere que não seja de abertura ou fechamento é ignorado (seu primeiro if dá a entender que é isso que você quer).

Repare que não precisei colocar um if específico para testar se o caractere não é abertura nem fechamento. Se ele for abertura, cai no if i in abertura, e se for fechamento, cai no elif i in fechamento. Se não for nenhum dos dois, não faz nada e vai para a próxima iteração do for.

Testando:

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

O problema está na linha 9 em pilha[-1]. Em algum momento da execução do programa, a lista pilha está vazia, ou seja, você está tentando acessar um item que não existe, gerando o IndexError.

Tente melhorar as suas condicionais de forma que a lista pilha não fique fazia ao chegar na condicional da linha 9 ou então acrescente à sua condição len(pilha) > 0. Exemplo:

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
1

Troque o return da função apresentada pelo hkotsubo pelo seguinte:

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

assim você poderá ver a string que foi passada para a função.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .