Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Задание про скобки на с++.

Ирина Ученик (187), закрыт 9 месяцев назад
Задача про скобки
Недавно в школе Петя прошел новую тему — правильные скобочные последовательности. Для него она показалась очень легкой и скучной. Учитель заметил его лень и дал ему задачу посложнее. У Пети есть строка s , состоящая из круглых скобок, и ему разрешается удалить не более одного символа таким образом, чтобы полученная строка являлась правильной скобочной последовательностью. Помогите Пете выяснить, сможет ли он решить задачу учителя. Напомним, что правильные скобочные последовательности определяются следующим образом: Пустая строка является правильной скобочной последовательностью Если S — правильная скобочная последовательность, то (S) также является правильной скобочной последовательностью Если S1 и S2 — правильные скобочные последовательности, то S1S2 также является правильной скобочной последовательностью
Формат входных данных: Единственная строка содержит строку s (1≤|s|≤106 ) — строка, которую учитель дал Пете. Строка состоит из символов «(» и «)».
Формат выходных данных: Выведите «Yes» (без кавычек), если Петя сможет решить поставленную задачу, или «No» в противном случае.
Лучший ответ
Андрей Высший разум (422110) 9 месяцев назад
 #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");
}
ПапаВысший разум (118785) 9 месяцев назад
Квадратичная сложность на такой тривиальной задаче...
Андрей Высший разум (422110) Папа, Да, задача тривиальна. Дописал в ответ решение O(n).
Володя МолонокиУченик (101) 9 месяцев назад
Сириус ни то ни другое не берет
Володя Молоноки Ученик (101) Володя Молоноки, извините, не туда написал
Володя МолонокиУченик (101) 9 месяцев назад
В сириусе на сотку
Спасибо
Остальные ответы
Hugin Мыслитель (8169) 9 месяцев назад
 #include    
int main()
{
int a = 0;
std::cin >> a;
if (a == 1)
{
std::cout << "Yes";
}
else
{
std::cout << "No";
}
return 0;
}
Вот выдает ес и ноу
ИринаУченик (187) 9 месяцев назад
программа выдает неверный ответ
при (()))()(()) выдает No, а не Yes...
Hugin Мыслитель (8169) Ирина, Да какая разница, ес или ноу, что то же пишет
ТрифонЗнаток (285) 9 месяцев назад
не работает
Володя МолонокиУченик (101) 9 месяцев назад
Это решение неверное
Простой набор синтаксиса плюсов
Hugin Мыслитель (8169) Володя Молоноки, Не надо так строго, я пока учусь только!
Похожие вопросы