2

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

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

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)
30n4
  • 21
  • Кстати, да, из постановки непонятно, что должно выводиться в случае (((), ведь это не последняя скобка нарушает последовательность, последняя скобка как-раз пытается выправить ситуацию, но не может сделать это только своими силами. Что нужно выводить в таком случае? – CrazyElf Dec 21 '22 at 06:25

3 Answers3

4

Описание самого оптимального алгоритма описано здесь: 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("Некорректная последовательность")
lomobit
  • 41
  • пожалуйста, постарайтесь оставлять чуть более развёрнутые ответы. дополнить ответ можно, нажав [edit] – aleksandr barakin Dec 21 '22 at 00:07
  • Ваш ответ можно улучшить с помощью дополнительной информации. Пожалуйста, нажмите [edit] для добавления подробностей, например, цитат или документации, чтобы другие могли подтвердить правильность вашего ответа. Вы можете найти дополнительную информацию о том, как писать хорошие ответы в Справке. – Дух сообщества Dec 21 '22 at 00:55
  • 2
    Для одного вида скобок это не самый оптимальный, проще подсчитывать баланс – MBo Dec 21 '22 at 01:22
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 в случае если есть незакрытые скобки.

TigerTV.ru
  • 3,225
  • Неправильно выводит номер скобки в последовательности "((()" – 30n4 Dec 21 '22 at 04:33
  • @30n4 А какой номер, по-вашему, должен быть? Выводите длину строки вместо -1, если в конце не сошлось – MBo Dec 21 '22 at 05:06
  • @30n4, ну, можно i+2 сделать, чтобы номер был за пределами возможных правильных значений. – TigerTV.ru Dec 21 '22 at 10:45
1

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

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 - если последовательность правильная.

TigerTV.ru
  • 3,225