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

Question

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

Рейтинг: 3Ответов: 2Опубликовано: 16.11.2014

Задача:
Некоторые скобочные структуры правильные, другие - неправильные. Ваша задача: определить, правильная ли скобочная структура.

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

}

Прошу помощи.

Обновление

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

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

c#

Источник: Stack Overflow на русском

Answer 1

▲ 4Принят

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

using namespace std;

int main(){
    string str;
    stack<char> 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;
}

Answer 2

▲ 4

Не помню решения этой задачи без рекурсии. Через рекурсию решается более-менее просто, вот так:

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>& braces) 
    {    
        int res = 0;
        for (auto& br : braces)
        {
            res += br.size();
        }
        return res; 
    }
    br_type _type;
    vector<Braces> _sub_braces;
};

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

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

Ответы