3

Estou resolvendo um exercício em Python em que tinha que validar uma expressão com base que os parênteses deviam fechar direito:

Crie um programa onde o usuário digite uma expressão qualquer que use parênteses. Seu aplicativo deverá analisar se a expressão passada está com os parênteses abertos e fechados na ordem correta.

Ex:

((a+b)*c)(x+y(3+2/3)*z) #é uma expressão válida
))(( #não é válida
6+)+85( #não é válida

Mas meu código sempre valida a expressão:

n1 = str(input('Digite uma expressão: ')).split()
for n2 in range(0, len(n1)):
    if n1[n2] == '(':
        for n3 in range(n2 + 1, len(n1)):
            if n1[n3] == ')':
                del n1[n2]
                del n1[n3]
                break
print(n1)
if '(' in n1:
    print('Expressão inválida')
elif ')' in n1:
    print('Expressão inválida')
else:
    print('expressão válida') 
0

2 Respostas 2

3

Se a ideia é somente verificar os parênteses (sem levar em conta se o restante é uma expressão aritmética válida), você só precisa de um contador, e de apenas um loop percorrendo os caracteres da string e atualizando este contador.

Se encontrar um (, incremente o contador em 1. Se encontrar um ), decremente o contador em 1. Se em algum momento o contador estiver negativo, quer dizer que foi encontrado um ) que não tem o ( correspondente (e aí nem precisamos verificar o restante).

Ao final do loop, se o contador for zero, é porque cada ( tem o seu ) correspondente e a expressão é válida:

expressao = input('Digite uma expressão: ')
cont = 0
for c in expressao:
    if c == '(':
        cont += 1
    elif c == ')':
        cont -= 1
    # se o contador é negativo, foi encontrado um ")" sem "(" correspondente
    if cont < 0:
        break # sai do for

if cont == 0:
    print('Expressão válida')
else:
    print('expressão inválida')

No for eu percorro os caracteres da string (repare também que não precisa de split, basta percorrer a string toda de uma vez). E para cada caractere, vou atualizando o contador conforme a lógica já explicada acima.

Se no meio do loop o contador ficar negativo, eu já sei que a expressão é inválida (tem um ) sem o respectivo () e nem adianta verificar o resto, por isso eu interrompo o loop com break.

Outro detalhe é que input já retorna uma string, então fazer str(input()) é redundante e desnecessário.


As outras respostas estão complicando desnecessariamente o algoritmo (obs: uma delas foi apagada). Ambas usam dois loops aninhados (um for dentro do outro, percorrendo a mesma string várias vezes desde o início) e várias chamadas de replace, que criam uma nova string.

Ou seja, além de loops desnecessários, são criadas várias strings durante o processo, o que torna os algoritmos bem ineficientes. No meu exemplo acima, só é feito um loop e nenhuma outra string é criada desnecessariamente. Só porque o código das outras respostas "funcionou", não quer dizer que sejam as melhores opções.

Uma delas - a que foi apagada - consegue ser ainda mais ineficiente, porque além de replace, ainda usa várias vezes split (que cria uma lista) e join (que junta a lista em uma string), além de usar index (que percorre a string desde o início, para encontrar o índice do elemento - e usar isso em um loop seguidas vezes torna o algoritmo muito ineficiente).

É claro que para poucas strings pequenas, a diferença será imperceptível (frações de segundos), mas rode algumas milhares de vezes e a diferença se mostrará de forma mais clara. Podemos fazer um teste simples com o módulo timeit:

def loops_aninhados(n1):
    for n2 in range(0, len(n1)):
        if n1[n2] == '(':
            for n3 in range(n2 + 1, len(n1)):
                if n1[n3] == ')':
                    n1 = n1.replace('(', 'o',1)
                    n1 = n1.replace(')', 'o', 1)
                    break
                    
    if '(' in n1:
        return False
    elif ')' in n1:
        return False
    else:
        return True

def loops_aninhados2(n1):
    for n2 in n1:
        if n2 == '(':
            for n3 in n1:
                if n1.index(n3) > n1.index(n2):
                    if n3 == ')':
                        n1 = ''.join(n1).replace(n2, '', 1).replace(n3, '', 1)
                        n1 = n1.replace('', ' ').strip().split(' ')
                        break
    if '(' in n1 or ')' in n1:
        return False
    else:
        return True

def loop_simples(n1):
    cont = 0
    for c in n1:
        if c == '(':
            cont += 1
        elif c == ')':
            cont -= 1
        # se o contador é negativo, foi encontrado um ")" sem "(" correspondente
        if cont < 0:
            return False

    return cont == 0

from timeit import timeit

# testando 100 mil vezes, com uma expressão válida e outra inválida
number = 100000
valida = '((a+b)*c)(x+y(3+2/3)*z)'
invalida = '6+)+85(x-y)+z(-13*2/23(r/4))'
print(timeit('loops_aninhados(valida)\nloops_aninhados(invalida)', number=number, globals=globals()))
print(timeit('loops_aninhados2(valida)\nloops_aninhados2(invalida)', number=number, globals=globals()))
print(timeit('loop_simples(valida)\nloop_simples(invalida)', number=number, globals=globals()))

timeit retorna o tempo de execução em segundos. O tempo exato varia conforme vários fatores (como o próprio hardware da máquina, se tinha outras coisas rodando ao mesmo tempo, etc), mas em geral, os loops aninhados são mais lentos (e o segundo, que usa split e join várias vezes, é mais lento ainda). Na minha máquina os tempos foram:

1.3530971
6.647586800000001
0.32360029999999895

Rodei algumas vezes e os tempos - e principalmente a proporção entre eles - foi similar: a primeira opção foi em média cerca de 3 a 4 vezes mais lenta (se comparada à minha solução), e a segunda foi cerca de 15 a 20 vezes mais lenta. No Repl.it os tempos foram diferentes, mas a diferença relativa entre eles foi similar.

Enfim, é como um dos nossos mais famosos usuários costuma dizer: "Funcionar é diferente de estar certo".


Por fim, vale dizer que usar for, split, join, replace e qualquer outro recurso da linguagem não é "errado" por si só. Mas é importante saber quando e como usá-los, e se tiver um algoritmo melhor, mais simples e eficiente, e que não precisa deles, não faz sentido continuar usando-os só porque "funcionou".

E lembrando mais uma vez que estas soluções só verificam os parênteses balanceados. Se a ideia fosse verificar se é uma expressão aritmética válida, aí precisaria de outra solução.

-5

Olá, Presado!! Quero ser sincero em dizer que a tua lógica está muito boa!

Eu fiz alguns ajustes no teu código para que funcione! Gostaria que preste atenção no código!!

n1 = str(input('Digite uma expressão: '))

for n2 in range(0, len(n1)):
    if n1[n2] == '(':
        for n3 in range(n2 + 1, len(n1)):
            if n1[n3] == ')':
                n1 = n1.replace('(', 'o',1)
                n1 = n1.replace(')', 'o', 1)
                break
                
if '(' in n1:
    print('Expressão inválida')
elif ')' in n1:
    print('Expressão inválida')
else:
    print('expressão válida') 

Espero ter ajudado!!

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 .