#include
#include
using namespace std;
int main() {
string p, s;
auto r = std::regex("\\(\\)");
getline(cin, s);
do {
p = s;
s = regex_replace(s, r, "");
} while (p != s);
cout << (s.size() < 2 ? "Yes" : "No");
}
Просто удаляем из строки все подстроки "()" - пока они есть.
В строке останутся только непарные скобки. И если их осталось меньше 2 - задача имеет решение.
Более производительный вариант, считающий баланс скобок за один проход по строке:
#include
using namespace std;
int main() {
string s;
getline(cin, s);
long p = 0, q = 0;
for (auto ch : s) {
if (ch == '(') {
++p; // Открывающая скобка
} else if (p) {
--p; // Закрывающая скобка, имеющая парную открывающую
} else {
++q; // Закрывающая скобка, не имеющая пары
}
}
cout << (p + q < 2 ? "Yes" : "No");
}
Недавно в школе Петя прошел новую тему — правильные скобочные последовательности. Для него она показалась очень легкой и скучной. Учитель заметил его лень и дал ему задачу посложнее. У Пети есть строка s , состоящая из круглых скобок, и ему разрешается удалить не более одного символа таким образом, чтобы полученная строка являлась правильной скобочной последовательностью. Помогите Пете выяснить, сможет ли он решить задачу учителя. Напомним, что правильные скобочные последовательности определяются следующим образом: Пустая строка является правильной скобочной последовательностью Если S — правильная скобочная последовательность, то (S) также является правильной скобочной последовательностью Если S1 и S2 — правильные скобочные последовательности, то S1S2 также является правильной скобочной последовательностью
Формат входных данных: Единственная строка содержит строку s (1≤|s|≤106 ) — строка, которую учитель дал Пете. Строка состоит из символов «(» и «)».
Формат выходных данных: Выведите «Yes» (без кавычек), если Петя сможет решить поставленную задачу, или «No» в противном случае.