Задача
Во многих прикладных задачах необходимо осуществлять различные операции со строками. Две достаточно часто встречающиеся операции — это разворот строки и конкатенация двух или нескольких строк.
В результате разворота строки $s$ получается строка $sR$, которая состоит из тех же символов, что и $s$, но идущих в обратном порядке. Например, в результате разворота строки «$abcde$» получается строка «$edcba$». Далее в этой задаче вместо обозначения $sR$ будет использоваться обозначение ($s$).
В результате конкатенации двух строк $s$ и $t$ получается строка $st$, в которой сначала записаны символы строки $s$, а затем — символы строки $t$. Аналогичным образом определяется конкатенация трех, четырех и большего числа строк. Например, при конкатенации строк «$abc$» и «$cda$» получается строка «$abccda$».
Ваша задача — определить результат конкатенации нескольких строк, часть из которых необходимо развернуть.
Входные данные
Состоит из единственной строки, которая содержит только строчные буквы латинского алфавита и круглые скобки. Ее длина не превышает $200$ символов. Эта строка описывает конкатенацию нескольких строк, часть из которых необходимо развернуть.
В заданной строке правее каждой открывающей скобки есть закрывающая, левее каждой закрывающей есть открывающая, причем между соответствующими друг другу открывающей и закрывающей скобками других скобок нет и обязательно есть хотя бы одна буква.
Выходные данные
Выведите результат конкатенации.
Тесты
| № | Входные данные | Выходные данные |
| 1 | russ(ai)(edocn)cup | russiancodecup |
| 2 | (bi).mazurok | ib.mazurok |
| 3 | acm.(cpci) | acm.icpc |
| 4 | Od(asse) | Odessa |
| 5 | (inu)ver(ytis) | university |
Код программы(string)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <iostream> using namespace std; void revers(string & str) { char a; cin.get(a); if (a != ')') revers(str); else return; str += a; } int main() { string str = ""; char a; while (cin.get(a)) if (a == '(') revers(str); else str += a; cout << str; return 0; } |
Код программы (c-string)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include <iostream> using namespace std; const int N = 200; void revers(char * res, int &n) { char a; cin >> a; if (a == ')') return; else revers(res, n); res[n++] = a; } int main() { char res[N]; char a; int n = 0; while (cin >> a) { if (a == '(') revers(res, n); else res[n++] = a; } for (int i = 0; i < n; i++) cout << res[i]; return 0; } |
Решение задачи
Перебираем каждый символ входной строки, как только встречаем ‘(‘ рекурсивно запоминаем каждый символ, вплоть до ‘)’. А на выходе из рекурсии добавляем эти символы в результирующую строку. Так как при выходе рекурсия будет выполнять сначала самый поздний свой вызов, а только после этого завершать более ранние, то добавляться символы будут в обратном порядке, что нам и нужно. Повторяем вышеописанные действия до конца данной строки.