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

#cpp

Задача:
Некоторые скобочные структуры правильные, другие - неправильные. Ваша задача: определить,
правильная ли скобочная структура.
Вход: Слово в алфавите из двух круглых скобочек ( и ), [, ], {, }. Длина слова меньше
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;

}

Прошу помощи.
Обновление
Программа работает, но на каких-то тестах она работает неправильно (при загрузке
в систему проходят не все тесты). Какие там тесты, мне не известно. И я не могу выяснить,
при каких условиях она ошибается, прошу помочь именно в этом.
Просто хочу научиться работать со стеком. Не подумал о Вашем примере. Попробовал
реализовать заново с помощью трех стеков, Ваш пример теперь работает правильно, но
снова не проходит все тесты в системе. Код изменил в ответе. Посмотрите, пожалуйста.    

Ответы

Ответ 1

Я не вижу, чтобы у вас использовался флаг 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;
}


Ответ 2

Не помню решения этой задачи без рекурсии. Через рекурсию решается более-менее просто,
вот так:
class Braces
{
public:
    enum class br_type 
    {
        _br_head,
        _br_round,
        _br_square,
        _br_figure
    };

    Braces(br_type type, char* line) : _type(type)
    {
        int runner = 0;
        while(line[runner] == '(' || line[runner] == '[' or line[runner] == '{')
        {
            if (line[runner] == '(')
                _sub_braces.push_back(Braces(br_type::_br_round, &line[runner + 1]));
            else if (line[runner] == '[')
                _sub_braces.push_back(Braces(br_type::_br_square, &line[runner + 1]));   
            else if (line[runner] == '{')
                _sub_braces.push_back(Braces(br_type::_br_figure, &line[runner +
1]));    
            runner += _sub_braces.back().size();
        }
        if (runner == strlen(line) && _type == br_type::_br_head)
            return;
        if (line[runner] == ')' && _type != br_type::_br_round)
            throw std::exception("NO");
        if (line[runner] == ']' && _type != br_type::_br_square)
            throw std::exception("NO");
        if (line[runner] == '}' && _type != br_type::_br_figure)
            throw std::exception("NO");     
    }
    int size() { return 2 + sum_sizes(_sub_braces); }
    int sum_sizes(vector& braces) 
    {    
        int res = 0;
        for (auto& br : braces)
        {
            res += br.size();
        }
        return res; 
    }
    br_type _type;
    vector _sub_braces;
};

Код написал тут, т.е. не проверял, но идея рекурсии, думаю, ясна. Если внешний объект
(с типом _br_head, которому передается вся строка) создатся без exception, то надо
выводить ОК, иначе сообщение exception-а. Сделав nasty эксепшны, можно даже указать,
на какой именно вложенности получена ошибка.


Ответ 3

#include 
#include 

#define TEST    1
#define VERBOSE 1

#if TEST
const char * testInput[] = {
    "[ ]",
    "{ }",
    "( )",
    "< >",
    "rth(zxc<[{e r}wer]fdg>zxc)hj",
    "il.)rge{ }",
    "sdl  fkv[flv,]",
    "fv[dsfnv>jn(bk) l",
    "(rg er>erg",
    "' }
};

int main(void)
{
    std::stack braceIndeces;
    std::string input;
    bool error = false;

#if TEST
  #if VERBOSE
    std::cout << "Running tests..."
              << std::endl << std::endl;
  #endif
    for (size_t testInputIdx = 0;
                testInputIdx < sizeof(testInput) / sizeof(testInput[0]);
                ++testInputIdx) {
        input = testInput[testInputIdx];
        std::cout << input << std::endl;
#else
  #if VERBOSE
    std::cout << "Enter char sequence with braces..."
              << std::endl << std::endl;
  #endif
    std::cin >> input;
#endif

        size_t inputIdx = 0;
        std::string::iterator itr = input.begin();
        for (; itr != input.end(); ++itr, ++inputIdx) {
            char ch = *itr;

            size_t currentBracesIdx = braceIndeces.empty()
                                    ? (size_t)-1
                                    : braceIndeces.top();

            for (size_t i = 0; i < sizeof(braces) / sizeof(braces[0]); ++i) {
                if (ch == braces[i][OpeningBrace]) {
                    braceIndeces.push(i);
                    break;
                }
                else if (ch == braces[i][ClosingBrace]) {
                    if (currentBracesIdx == i)
                        braceIndeces.pop();
                    else { // error
                        error = true;
                        if (currentBracesIdx == (size_t)-1) {
#if VERBOSE
                            std::cout << "Error: unexpected brace char '"
                                      << ch << "' at "
                                      << inputIdx
                                      << ", braces not opened"
                                      << std::endl << std::endl;
#else
                            std::cout << "NO" << std::endl << std::endl;
#endif
                        }
                        else {
#if VERBOSE
                            std::cout << "Error: unexpected brace char '"
                                      << ch
                                      << "' at " << inputIdx
                                      << ", should be '"
                                      << braces[currentBracesIdx][ClosingBrace]
                                      << "'"
                                      << std::endl << std::endl;
#else
                            std::cout << "NO" << std::endl << std::endl;
#endif
                        }
                    }
                    break;
                }
                // else tested char is not a brace char
            }
            if (error)
                break;

        }

        if (error)
            error = false;
        else {
            if (!braceIndeces.empty()) {
#if VERBOSE
                std::cout << "Error: unclosed braces, '"
                          << braces[braceIndeces.top()][ClosingBrace]
                          << "' expected at the end"
                          << std::endl << std::endl;
                braceIndeces = std::stack();
#else
                std::cout << "NO" << std::endl << std::endl;
#endif
            }
            else
                std::cout << "YES" << std::endl << std::endl;
        }
#if TEST
    }
#endif

    return 0;
}