Рассмотрим правильную скобочную последовательность, в которой любая пара () скобок может содержать внутри себя буквы — например (qwe) или (qwe)()((rty)(uio)). Применим к ней следующий рекурсивный алгоритм:
Если строка — это скобочная последовательность, содержащая единственную пару скобок (в начале и конце), просто выведем всю строку со скобками
- Если строка — это скобочная последовательность, между начальной и конечной скобкой которой находится другая скобочная последовательность, обработаем её нашим алгоритмом (не забудем вывести скобки)
Если строка образована приписыванием друг к другу нескольких скобочных последовательностей типа 1 или 2, применим наш алгоритм к каждой из них в порядке от последней до начальной
Написать итеративный алгоритм решения этой задачи — функцию backwards(char *str), которая выводит скобочную последовательность с буквами, преобразованную в соответствии с правилами. Тестирующая программа может выглядеть так:
(qwe)(()((rty)(uio)))
Эта строка содержит две скобочные последовательности — (qwe) и (()((rty)(uio))) — тип 1 и 2 соотв.
Начнём с последней, которая тоже содержит две — () и ((rty)(uio)) — снова 1 и 2)
Вторая из них содержит опять две — (rty) и (uio) — обе 1
Надо вывести (uio), затем (rty)
- …со скобками вокруг них
затем выводим ()
- ещё пара скобок вокруг
Вот мы и добрались до (qwe), которую тоже выводим
(((uio)(rty))())(qwe)
- Подсказка — в действительности это очень простой алгоритм! Просто посмотрите на вывод!
- Подсказка: сравнительно несложно проделать несколько примеров вручную или написать рекурсивную функцию: просматриваем строку с конца по типу 3, для каждой ПСкП (они будут типа 1 или 2) обработаем её.
(нажмите «Комментарии» в шапке страницы, чтобы прочитать спойлер)
