Python. Как убрать лишние / неправильные скобки в строке

Question

Например, входная строка:

s = "fo)o)fus()(bar((em)ro(em))dah((y(XXX)"

В результате я ожидаю:

fus()((em)ro(em))dah(XXX)

Это как результат должен содержать все "здоровые" блоки, между которыми есть открытый "(" и закрытый ")" + "здоровый" текст. Все больные части должны быть удалены: "fo)" и "o)", потому что они не включены в "()" и не находятся между "()" или не включены в "()"

Еще один пример для проверки:

z = "))(OMG)123(()qwe(zxc)(ll"

должен вернуться(OMG)123()qwe(zxc)

Я буду, что это может быть решено как с re Модуль как обычный скрипт. Но я понятия не имею, какой алгоритм следует использовать.

PS: я не откажусь от любой помощи.:)

Answer 1

Есть очень хороший пример использования стеков, и почти каждый студент CS решил это хотя бы один раз. Проверьте это в качестве примера, но вы можете найти гораздо лучший синтаксис (специально написанный для C++).

Эти решения обычно предназначены для проверки правильности утверждения или нет, но вы можете использовать ту же логику, чтобы удалить неправильные части и сохранить только те, которые соответствуют. Так что просто создайте новую строковую переменную (variable=""), переберите строку и проверьте скобки, если они находятся в правильном месте, добавьте их в эту переменную. Чтобы проверить порядок скобок, используйте объект Stack, когда вы увидите открывающую скобку, поместите ее в стек и затем продолжите, когда она закроет единицу, затем вытолкните последнее значение из стека и проверьте (новый элемент ) и последний элемент в стеке должен быть (). Если они не совпадают, отбросьте эту часть и продолжайте, если они совпадают, добавьте эту часть в строку.