Problem with balance of parentheses, in Python

Question

Galera to with the following code:

exp = str(input('Digite a expressão: '))
pilha = []
for simb in exp:
    if simb == '(':
        pilha.append('(')
    elif simb == ')':
        if len(pilha) > 0:
            pilha.pop()
    else:
        if simb == ')':
            pilha.append(')')
            break

if len(pilha) == 0:
    print('Sua expressão está "Correta"!')
else:
    print('Sua expressão está "Errada"!')

If you run the code by putting as an example:

(((2*2)-1)*(1+4)) assim parece correto
(((2*2)-1)*(1+4))) com parentese a mais do lado direito também aparece correto
((((2*2)-1)*(1+4)) agora com um parentese a mais do lado esquerdo aparece errado
ou seja ficou 
((())()) aparece certo
((())())) aparece certo
(((())()) aparece errado

Where am I going wrong?

Answer 1

It is a problem known as parenthesis, and the most common solutions suggest stack, queue and disposal. ^{1 2 3}

First let’s get to the problem in your code:

    elif simb == ')':
        if len(pilha) > 0:
            pilha.pop()
    else:
        if simb == ')':
            pilha.append(')')
            break

The part else: if simb == ')': is similar elif simb == ')':, so it will never be executed, since the condition is satisfied in Elif.

The problem is when you find len(pilha) == 0 (or the else of condition if len(pilha) > 0, you ignore, but this is first of all an unbalanced parentheses, ie a closing before opening.

To fix this you can just change the else as part of if len(pilha), getting:

for simb in exp:
    if simb == '(':
        pilha.append('(')
    elif simb == ')':
        if len(pilha) > 0:
            pilha.pop()
        else:
           pilha.append(')')
           break

Below another way to solve a little more didactic, with counter:

abertos = 0
for c in exp:
    if c == '(':
        abertos += 1
    elif c == ')':
        abertos -= 1
        if abertos < 0:
            break

print('balanceado' if abertos == 0 else 'desbalanceado')

Answer 2

In a free translation of that article in wikpedia (in English is strange) "Parentheses matching, Brace matching or Bracket matching refers to the feature called "syntax highlighting"that certain editors of texts and development environments offer highlighting the openings and closing of braces (parentheses, brackets, or keys)". As the article says, the concept encompasses the opening and closing not only of the parentheses, but also of the other "braces", I present below an algorithm for this problem and then the encoding in python.

Algorithm:

1. Go through the entire expression by checking each character;
2. If the character is not a Bracket, ignore;
3. If it’s an opening rack, add it to the stack;
4. If it is a closing racket:
   4.1 Return False if the last character of the stack is not a corresponding opening Bracket;
5. Remove the corresponding opening Bracket from the battery;
6. In the end return True if the battery is empty, if it does not return False.

Python code:

def parenthesis_matching(brackets):
    __open = ['(', '{', '[']
    __close = [')', '}', ']']
    __stack = []
    if brackets=='':
        return False
    for b in brackets:
        if b in __open:
            __stack.append(b)
        elif b in __close:
            if __stack==[]:
                return False
            open_b = __open[ __close.index(b) ]
            last = __stack.pop()
            if not open_b == last:
                return False
    return True if __stack==[] else False     

# Expressoes para testar o código    
exps = []
exps.append('(a[0]+b[2c[6]]) {24+53}')
exps.append('f(e(d))')
exps.append('[()]{}([])')
exps.append('((b)')
exps.append('(c]')
exps.append('{(a[])')
exps.append('([)]')
exps.append(')(')
exps.append('{[(stackoverflow),(parenthesis_matching(brackets))]}')

# Testando o codigo
for e in exps:
    print(e+' : ', parenthesis_matching(e))

Exit:

(a[0]+b[2c[6]]) {24+53} :  True
f(e(d)) :  True
[()]{}([]) :  True
((b) :  False
(c] :  False
{(a[]) :  False
([)] :  False
)( :  False
{[(stackoverflow),(parenthesis_matching(brackets))]} :  True

See working on repl.it.