Задача на скобочки

Задача: Некоторые скобочные структуры правильные, другие - неправильные. Ваша задача: определить, правильная ли скобочная структура. Вход: Слово в алфавите из двух круглых скобочек ( и ), [, ], {, }. Длина слова меньше 40001. Выход: Либо 'NO', либо 'YES' без кавычек. Вот текст моей программы, но она не проходит все тесты. Не пойму, где ошибка. И какие тесты она не проходит (не смог таких придумать). int main() { std::string s; std::cin >> s; std::stack < char > st; std::stack < char > st1; std::stack < char > st2;
bool f = true, g = true, k = true; int index = 0;
while (index < s.length() && f && g && k) { if (s[index] == ')') { f = (!st.empty()); if (f) st.pop(); } else if (s[index] == ']') { g = (!st1.empty()); if (g) st1.pop(); } else if (s[index] == '}') { k = (!st2.empty()); if (k) st2.pop(); } else if (s[index] == '(') { st.push(s[index]); } else if (s[index] == '[') { st1.push(s[index]); } else if (s[index] == '{') { st2.push(s[index]); }
index++; } std::cout << (((k && f && g && st.empty() && st1.empty() && st2.empty()) ? "YES" : "NO")) << std::endl;
} Прошу помощи. Обновление Программа работает, но на каких-то тестах она работает неправильно (при загрузке в систему проходят не все тесты). Какие там тесты, мне не известно. И я не могу выяснить, при каких условиях она ошибается, прошу помочь именно в этом. Просто хочу научиться работать со стеком. Не подумал о Вашем примере. Попробовал реализовать заново с помощью трех стеков, Ваш пример теперь работает правильно, но снова не проходит все тесты в системе. Код изменил в ответе. Посмотрите, пожалуйста.

Ответ

Я не вижу, чтобы у вас использовался флаг k в проверке while. Как вы думаете, что произойдет при входе "[{))" в вашу программу и является ли это правильным. Не указаны критерии правильности скобочных структур, к примеру, могут ли они быть пересекающимися. По хорошему, вам нужно считать количество каждого вида скобок, без всяких стеков и прочих наворотов: int round=0, rect=0, figure=0; Если опустилось ниже 0 во время прохождения, значит ошибка в структуре скобок и выполнить break, если по окончанию строки не все стали, снова равны нулю, тоже ошибка. UPDATE 1 (неверный) Тогда можно ограничиться одним стеком и организовать проверку только выталкиваемого из стека значения pop(), чтобы оно содержало аналогичную открывающую скобку. Ясли не ошибаюсь, этого достаточно: if (s[index] == ')') f = (!st.empty() && st.pop()=='('); if (s[index] == ']') g = (!st.empty() && st.pop()=='['); if (s[index] == '}') k = (!st.empty() && st.pop()=='{'); if (s[index]=='['||s[index]=='{'||s[index]=='(') st.push(s[index]); Соответственно проверка флагов в цикле и при выводе ответа (+ на пустоту стека) остается. UPDATE 2 (исправленный) @doomsday, прошу прощения, я не часто имею дело с С++, для возврата значения из стека надо использовать вместо pop() функция top(). То есть по идее следующий код должен решать поставленную задачу. #include #include #include
using namespace std;
int main(){ string str; stack st; int index = 0; bool f = true, g = true, k = true;
cin >> str;
while (index < str.length() && f && g && k) { char chr = str[index]; if (chr == '[' || chr == '{' || chr == '(') st.push(chr); if (chr == ')') f = (!st.empty() && st.top() == '('); if (chr == ']') g = (!st.empty() && st.top() == '['); if (chr == '}') k = (!st.empty() && st.top() == '{'); index++; }
cout << (k && f && g && st.empty() ? "YES" : "NO") << endl;
return 0; }