LecturesCMC/AL/Prac/Homework_RevBraces

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

1. Если строка — это скобочная последовательность, содержащая единственную пару скобок (в начале и конце), просто выведем всю строку со скобками

2. Если строка содержит несколько скобочных последовательностей, применим наш алгоритм к каждой из них в порядке от последней до начальной, не забывая выводить их скобки

Написать итеративный алгоритм решения этой задачи — функцию backwards(char *str), которая выводит скобочную последовательность с буквами, преобразованную в соответствии с правилами. Тестирующая программа может выглядеть так:

•    1 #include <stdio.h>
     2 #include <stdlib.h>
     3 int main(void) {
     4         char *s;
     5         size_t n, l;
     6         l = getline(&s, &n, stdin);
     7         s[l-1] = 0;
     8         backwards(s);
     9         free(s);
    10         return 0;
    11 } 
  

(qwe)(()((rty)(uio)))

• Эта строка содержит две скобочные последовательности — (qwe) и (()((rty)(uio)))

  • Начнём с последней, которая тоже содержит две — () и ((rty)(uio))

    • Вторая из них содержит опять две — (rty) и (uio)

      • Надо вывести (uio), затем (rty)`

        • …и скобки вокруг них
    • затем выводим пустую строку и скобки вокруг неё
  • ещё пара скобок вокруг

• Вот мы и добрались до (qwe), которую тоже выводим

(((uio)(rty))())(qwe)

• Подсказка — в действительности это очень простой алгоритм! Просто посмотрите на вывод!

CategoryHomework