Правильность скобочной последовательности. Номер скобки нарушающей последовательность

Question

Нужно написать программу, которая определяет, является ли введенная скобочная структура правильной. Примеры правильных скобочных выражений: (), (())(), ()(), ((())), неправильных — )(, ())((), (, )))), (((). Найти порядковый номер первого символа (скобки), нарушающего правильность расстановки скобок.

Код не работает правильно с последовательностью "((()" и не знаю как выводить информацию о том, что последовательность правильная.

list = list(input("Введите последовательность скобок:>"))
stack = []
index = 0
count_open = 0
count_close = 0

for i in range(len(list)):
    if (len(list) == 1):
        index += 1
        break
    if count_close <= count_open:
        if (list[i] == ')'):
            index += 1
            count_close += 1
            if bool(stack) == True:
                index += 1
                stack.pop()
            elif bool(stack) == False:
                break
        elif (list[i] == '('):
            count_open += 1
            stack.append(list[i])
        if (len(list) == count_open):
            index += 1
            break;
        elif (len(list) == count_close):
            index += 1
            break;
    else:
        break
print(index)

Answer 1

Описание самого оптимального алгоритма описано здесь: https://ru.stackoverflow.com/a/682164/369565

Прикладываю пример реализации

inputString = input("Введите последовательность скобок: ")
stack = []
correct = True

for char in inputString:
    if char == '(':
        stack.append('(')
    elif char == ')':
        if len(stack) == 0:
            correct = False
            break
        elif stack[-1] == '(':
            stack.pop()

if (correct and len(stack) == 0):
    print("Корректная последовательность")
else:
    print("Некорректная последовательность")

Answer 2

Можно так:

from itertools import accumulate

def incorrect(s):
    it = accumulate(map({'(' : 1, ')' : -1}.__getitem__, s))
    for i, x in enumerate(it):
        if x < 0:
            return i + 1
    if x != 0:
        return i + 2
    return -1
    

s = input('Bведите скобочную последовательность: ')
print(incorrect(s))

Выводит порядковый номер некорректной скобки (<= длина последовательности), -1 - если последовательность правильная, и длину последовательности+1 в случае если есть незакрытые скобки.

Answer 3

Другой вариант:

def incorrect(s):
    stack = []
    for i, c in enumerate(s):
        if c == '(':
            stack.append(i)
        elif c == ')':
            try:
                stack.pop()
            except IndexError:
                return i + 1
    if len(stack) != 0:
        return stack.pop() + 1
    return -1   
    
s = "(()()"
print(incorrect(s)) # 1

Выводит порядковый номер некорректной скобки, -1 - если последовательность правильная.

БЛОГ НА HUSL

Правильность скобочной последовательности. Номер скобки нарушающей последовательность

Ответы (3 шт):