Не могу найти решение с алгоритмом в Python

Question

Задача в том, чтобы скобки ()[]{} правильно были расставлены в строке. Если порядок неверный, то выводить ошибку. Я сделал фильтр и идея была пройти по строке и если текущий элемент и следующий элемент составляют пару, например ( ) то удалить их из строки или заменить. Но выдается ошибка string index out of range.

f1 = "([1+1]+(2*2)-{3/3})"
bt = {'{': '}', '[': ']', '(': ')'}
f2 = "".join(filter(lambda x: x in bt or x in bt.values(), f1))

for i in range(0, len(f2) - 1):
    if f2[i] in bt and f2[i + 1] in bt.values():
       f2 = f2[i].replace('{}', '').replace('()', '').replace('[]', '')

print(f2)

Answer 1

Причина ошибки в том, что в текущем примере у вас диапазон от 0 до 2 и списки трехэлементные (элементы номер 0, номер 1, номер 2), а вы в f2 [i+1] пытаетесь брать элемент номер 3, которого нет.

Answer 2

Первым делом нужно ставить везде отладочную печать. Посмотрим, что у вас получается в f2: ([](){}). Перебираем в цикле по i символы из f2. Пары i - f2[i],f2[i+1]:

0 - ([
1 - []

Вот в этот момент срабатывает if и выполняется эта строка:

f2 = f2[i].replace('{}', '').replace('()', '').replace('[]', '')

В f2[i] в этот момент находится [, она, конечно, ни на что не заменяется - это же один символ, а тут замена парных скобок. В итоге f2 присваивается [, ну и дальше выход индекса за границы, потому что дальше i будет 2, а в f2 всего один символ.

Но замена этой строки на f2 = f2.replace... тоже не исправит ситуацию до конца - замены будут правильные, но размер f2 уменьшится до 2, и следующий индекс 2 опять выйдет за границы строки.

В общем, вам тут весь алгоритм менять надо.

Answer 3

Как вам уже сказали - тут весь алгоритм менять надо. Добавлю от себя: изобретение велосипеда - вещь конечно захватывающая, но малопродуктивная. Все-таки всегда лучше сначала тему изучить, а уж потом браться за решение задач. Тем более, что интернет полон и описаний этой задачи и примеров ее реализации. Вот нашел у себя в записках одно из возможных решений. Для общего случая - подставляйте какие хотите скобки, делайте сколько угодно вложенностей в выражениях. Ловит любую несбалансированность скобок. Откуда когда-то скачал - не помню, на авторство не претендую. Но - работает. Внимательно изучив алгоритм, можно и самому многое понять и многому научиться.

def brackets_check(input_str):
    s = []
    balanced = True
    index = 0
    while index < len(input_str) and balanced:
        symbol = input_str[index]
        if symbol in "([{":
            s.append(symbol)
        else:
            if s == []:
                balanced = False
            else:
                top = s.pop()
                if not matches(top,symbol):
                       balanced = False
        index = index + 1
    if balanced and s==[]:
        return True
    else:
        return False

def matches(open,close):
    opens = "([{"
    closers = ")]}"
    return opens.index(open) == closers.index(close)

Пример работы Вызов

print(brackets_check('{(){}[({})]}'))

Результат

True

Вызов

print(brackets_check('{(){[({})]}'))

Результат

False

Если в нем что-то немного не так (или не то) как вы хотите - то всегда можно самому соответствующим образом "оттюнинговать". Ну например, удалить все "не скобки" из выражения можно вот так:

s = "{(a+b)+[25+5*(7/4)]}"
s1 = "".join(c for c in s if c in "{}[]()")
print (s1)

Результат:

{()[()]}

А дальше - вышеприведенным алгоритмом.

Удачи.

БЛОГ НА HUSL

Не могу найти решение с алгоритмом в Python

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