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

3 ответа 3

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("Некорректная последовательность")
3
  • пожалуйста, постарайтесь оставлять чуть более развёрнутые ответы. дополнить ответ можно, нажав править 21 дек 2022 в 0:07
  • Ваш ответ можно улучшить с помощью дополнительной информации. Пожалуйста, нажмите править для добавления подробностей, например, цитат или документации, чтобы другие могли подтвердить правильность вашего ответа. Вы можете найти дополнительную информацию о том, как писать хорошие ответы в Справке. 21 дек 2022 в 0:55
  • 2
    Для одного вида скобок это не самый оптимальный, проще подсчитывать баланс
    – MBo
    21 дек 2022 в 1: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 в случае если есть незакрытые скобки.

3
  • Неправильно выводит номер скобки в последовательности "((()"
    – 30n4
    21 дек 2022 в 4:33
  • @30n4 А какой номер, по-вашему, должен быть? Выводите длину строки вместо -1, если в конце не сошлось
    – MBo
    21 дек 2022 в 5:06
  • @30n4, ну, можно i+2 сделать, чтобы номер был за пределами возможных правильных значений.
    – TigerTV.ru
    21 дек 2022 в 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 - если последовательность правильная.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.