стэк | C++ для приматов

Условие

(Ссылка на задачу в e-olymp)

Имеется строка, содержащая скобки () и []. Скобочное выражение считается правильным, если:

оно является пустым
если A и B правильны, то AB правильно
если A правильно, то (A) и [A] правильны

Напишите программу, которая по входной строке, содержащей скобочное выражение, определит корректно ли оно. Длина строки не больше 128 символов.

Входные данные

Первая строка содержит количество тестов n. Каждая из следующих n строк содержит выражение, состоящее из скобок () и [].

Выходные данные

Для каждого теста вывести в отдельной строке «Yes«, если выражение является правильным и «No» иначе.

Тесты

3
([])
(([()])))
([()[]()])()

Yes
No
Yes

(тесты взяты с e-olymp.com)

Результаты задачи № 2479

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main()
{
    int n;
    cin >> n;
    char l;
    cin.get(l); //считывание конца строки после числа
    for(int z=0;z<n;z++){
        bool q=1; //переменная "фиксирующая" ошибку
        char hab;
        string str;
        getline(cin,str); //используем, чтобы читать до конца строки
        int j=str.size(); //размер строки ( кол-во обрабатываемых символов)
        stack<char> res; //стэк скобок
        for(int i=0;i<j;i++){
            if((str[i]=='(')||(str[i]=='[')) //если открывающая скобка - то кладем в стэк
                res.push(str[i]);
            else{ //если закрывающая скобка
                    if(!res.empty()){ //если стэк не пуст
                        hab=res.top(); //вытаскиваем последний элемент
                        if(str[i]==')'){ //сверяем на типы скобок
                            if(hab=='('){
                                res.pop(); //удаляем пару
                               }
                            else{
                                q=0;
                                cout << "No" << endl;
                                break;

                            }
                        }
                        else{
                            if(hab=='['){ //второй тип скобок (те же действия)
                                res.pop();
                               }
                            else{
                                q=0;
                                cout << "No" << endl;
                                break;
                            }
                        }
                    }
                    else{ //если стэк пуст  - то ошибочка вышла!
                        cout << "No" << endl;
                        q=0;
                        break;
                    }
            }
        }
        if(q){
        if(res.empty()) //собственно ответ
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
        }

    }
    return 0;
}

#include <iostream>

#include <stack>

#include <string>

using namespace std;

int main()

{

int n;

cin >> n;

char l;

cin.get(l); //считывание конца строки после числа

for(int z=0;z<n;z++){

bool q=1; //переменная "фиксирующая" ошибку

char hab;

string str;

getline(cin,str); //используем, чтобы читать до конца строки

int j=str.size(); //размер строки ( кол-во обрабатываемых символов)

stack<char> res; //стэк скобок

for(int i=0;i<j;i++){

if((str[i]=='(')||(str[i]=='[')) //если открывающая скобка - то кладем в стэк

res.push(str[i]);

else{ //если закрывающая скобка

if(!res.empty()){ //если стэк не пуст

hab=res.top(); //вытаскиваем последний элемент

if(str[i]==')'){ //сверяем на типы скобок

if(hab=='('){

res.pop(); //удаляем пару

}

else{

q=0;

cout << "No" << endl;

break;

}

else{

if(hab=='['){ //второй тип скобок (те же действия)

res.pop();

}

else{

q=0;

cout << "No" << endl;

break;

}

else{ //если стэк пуст - то ошибочка вышла!

cout << "No" << endl;

q=0;

break;

}

if(q){

if(res.empty()) //собственно ответ

cout << "Yes" << endl;

else

cout << "No" << endl;

}

return 0;

}

Алгоритм

Решение задачи состоит в последовательной обработке каждого символа. Мы читаем символ. Если это открывающая скобка — то кладем в стэк. Если закрывающая — смотрим последний элемент в стэке. Если скобка «находит пару» — то удаляем их обоих. В противном случае — это ошибка. Если же после обработки всех символов в стэке останется скобки — то значит в строке было больше открывающих скобок, и такая строка — не правильная.

Маленький костыль для этой задачи — это лишнее считывание символа в самом начале. Делается это для того, чтобы дальше, мы спокойно могли использовать функцию getline, которая читает строку до символа конца строки. Эти дополнительным вводом, мы как бы забираем на себя символ конца строки стоящий после числа, определяющее кол-во строк.

Ссылка на ideone.com