Задача "Строки и скобки"

Дана строка, содержащая только английские буквы (большие и маленькие). Добавить открывающиеся и закрывающиеся скобки по следующему образцу: examplee(x(a(m)p)l)e До середины добавляются открывающиеся скобки, после середины – закрывающиеся. В случае, когда длина строки четна, в скобках, расположенных в середине, должно быть 2 символа: cardc(ar)d , но не c(a()r)d .

В уроке написано решать через рекурсию, но я не пойму как ее туда внедрить.

1 лайк

ну давай сделаем так: пусть f(s) - ответ для s
Базовый случай: |s| \leq 2
если |s| = 1 (s = "a")\implies f(s) = "(a)"
если |s| = 2 (s = "ab") \implies f(s) = "(ab)"
Теперь |s| \geq 3
Если s = a_1a_2 \ldots a_{n-1}a_n то f(s) = "(a_1" + f(a_2\ldots a_{n-1}) + “a_n)”
Это и есть наша рекурсия

6 лайков

Если s = a_1a_2 \ldots a_{n-1}a_ns=a 1​a 2​…a n−1 a n то f(s) = “(a_1” + f(a_2\ldots a_{n-1})f(s)=" ) + “a_n)”
Как написать эту строку в C++ ?

Ща, я разберусь как код красивым сделать, а пока так

string f(string s){
	string p, r, k;
	r = "(" + s + ")";
	if (s.size() < 3) return r;
	for(int i = 1; i < s.size() - 1; ++i) p += s[i];
	k = "(";
	r = k + s[0] + f(p) + s[s.size() - 1] + ")";
	return r;
}

что я заметил, во время написания этой штуки, то что у C++ какая то шиза и он символ "(" заменяет на какую то абракадабру, поэтому я его запихиваю в переменную k

нет такого :0

а тут в чем мем? (последняя строчка ответ)

string f(string s){
	string p, r;
	r = "(" + s + ")";
	if (s.size() < 3) return r;
	for(int i = 1; i < s.size() - 1; ++i) p += s[i];
	cout << p << endl;
	r = "(" + s[0] + f(p) + s[s.size() - 1] + ")";
	return r;
}

Screenshot 2022-11-12 172544

1 лайк

r = "(" + s[0] + f(p) + s[s.size() - 1] + ")";
Тут если заменить “(” на “)” тоже самое будет, думаю косяк не в скобочке. А в том что ты потом char (s[0]) добавляешь и происходит шиза с типами, если заменить s[0] на s.substr(0, 1) то всё норм будет.

1 лайк

это как в питоне с туплами походу)) сколько людей на этом погорело))