скобочная последовательность

191

06 мая 2018, 20:09

когда строка начинаеться ")" с этой скобкой выдает ошибку или с этой "}" что делать?

#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b, c;
    stack <int> p;
    string s;
    cin >> s;
    a = s.size();
    for(int i = 0; i < a; i++){
        if(s[i]=='(' || s[i] == '{'){
            p.push(i);
        }else{
            if(s[i] == ')'){
                p.pop();
            }else{
                if(s[i] == '}'){
                    p.pop();    
            }
        }
    }
}
    if(p.size() == 0){
        cout << "YES";
    }else{
        cout << "NO";
    }
}

Answer 1

У вас проблема вот здесь:

}else{
    if(s[i] == ')'){
        p.pop();
    }else{
        if(s[i] == '}'){
            p.pop();    
    }
}

Если первая скобка закрывающая, то вы удаляете не существующий элемент стэка. К тому же вы не верно реализуете свой алгоритм. Вы удаляете из стэка в любом случае, в то время, как должны только если последняя в стэке скобка является открывающей. Иначе скобочная последовательность не может быть правильной. А в случае вашей реализации, достаточно просто равного количества открывающих и закрывающих скобок, при чем не важно какого вида, и тогда прога выдаст, что это правильная скобочная последовательность, хотя она таковой не является.

Вот исправленная версия кода (корявая, но рабочая), которая определяет является ли скобочная последовательность верной:

#include <bits/stdc++.h>
using namespace std;
int main() {
    stack <int> p;
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++){
        if(s[i]=='(' || s[i] == '{'){
            p.push(s[i]);
        }
        else{
            if(s[i] == ')' && !p.empty() && p.top() == '(') {
                p.pop();
            }
            else if (s[i] == '}' && !p.empty() && p.top() == '{') {
                p.pop();
            }
            else if ((s[i] == '}' || s[i] == ')') && p.empty()) {
                p.push(i);
                break;
            }
        }
    }
    if(p.empty()){
        cout << "YES\n";
    }else{
        cout << "NO\n";
    }
}