Paranteze corect închise în C++: verificare liniară

Șirul (()()) este corect parantezat, iar )( nu este. Ambele pot avea la fel de multe deschideri și închideri, dar numărul total nu este suficient. O închidere trebuie să aibă deja o deschidere disponibilă în stânga ei.

Contractul exact

Citim o linie de cel mult 1000 de caractere, alcătuită exclusiv din ( și ). Șirul gol este considerat corect. Afișăm DA sau NU. Nu acceptăm acolade, paranteze pătrate, litere ori spații în această variantă a problemei.

Tabloul char are capacitatea 1001, pentru maximum 1000 de paranteze și terminator. Varianta string respectă aceleași limite ale intrării, chiar dacă reprezentarea poate crește dinamic.

După fiecare caracter din (()()), numărul parantezelor deschise încă neînchise este 1,2,1,2,1,0.Mărește schema ↗

Două condiții necesare împreună

La o deschidere mărim nivelul; la o închidere îl micșorăm. Nivelul reprezintă numărul deschiderilor încă neînchise. El nu trebuie să fie negativ după niciun prefix și trebuie să fie zero la final.

Pentru (()()), nivelurile sunt 1, 2, 1, 2, 1, 0. Pentru )(, primul nivel este -1, deci respingem imediat. Pentru ((), niciun prefix nu este negativ, dar nivelul final este 1: lipsește o închidere.

Varianta cu char[]

#include <iostream>
using namespace std;
int main() {
    char s[1001]; cin.getline(s,1001);
    int nivel=0; bool corect=true;
    for(int i=0;s[i]!='\0';++i) {
        if(s[i]=='(') ++nivel; else --nivel;
        if(nivel<0) { corect=false; break; }
    }
    cout << (corect && nivel==0 ? "DA\n" : "NU\n");
}

Varianta cu std::string

Parcurgerea directă a caracterelor înlocuiește testul manual al terminatorului. Sensul nivelului și cele două condiții rămân identice.

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s; getline(cin,s);
    int nivel=0; bool corect=true;
    for(char c : s) {
        if(c=='(') ++nivel; else --nivel;
        if(nivel<0) { corect=false; break; }
    }
    cout << (corect && nivel==0 ? "DA\n" : "NU\n");
}

De ce ajunge un contor

Avem un singur tip de paranteză. Orice închidere poate închide ultima deschidere rămasă, iar pentru validitate este suficient să știm că aceasta există. Dacă toate prefixele au nivel nenegativ, fiecare închidere găsește o deschidere. Nivelul final zero garantează că nu rămâne nicio deschidere nefolosită.

Cu mai multe tipuri, un contor nu este suficient. Șirul ([)] are numere egale de deschideri și închideri, dar tipurile se intersectează greșit. Atunci trebuie păstrată ordinea deschiderilor într-o stivă și verificat tipul ultimei paranteze deschise.

Timpul este O(n), cu oprire mai devreme la primul prefix invalid. Memoria auxiliară a verificării este O(1), pe lângă textul citit. Nu folosim recursivitate, deci lungimea intrării nu consumă stiva de apeluri.

Exersează

Verifică ()(), ((())), ((), ())( și linia goală. Răspunsurile sunt DA, DA, NU, NU, DA. Ultimul caz este decis de convenția explicită din cerință, nu de un accident al implementării.

Extinde programul pentru a raporta adâncimea maximă numai când șirul este valid. Pentru (()()), adâncimea este 2. Păstrează separat maximul nivelului, dar nu afișa o adâncime ca rezultat valid după ce ai detectat o închidere fără pereche.

Recapitulează stiva și ordinea LIFO, reprezentarea textului și diferența față de stiva apelurilor.

Întrebări frecvente

Cum verific dacă un șir de paranteze rotunde este corect?

Numără deschiderile încă neînchise: crește contorul la ( și scade-l la ). El nu trebuie să fie negativ după niciun prefix și trebuie să fie zero la final.

De ce nu ajunge același număr de deschideri și închideri?

Ordinea contează. Șirul )( are câte o paranteză de fiecare fel, dar începe cu o închidere fără pereche. Verificarea fiecărui prefix detectează această eroare.

Este suficient un contor pentru mai multe tipuri de paranteze?

Nu. Pentru tipuri diferite trebuie verificată și ordinea închiderii. O stivă păstrează ultima deschidere neînchisă; astfel poate respinge, de exemplu, șirul ([)].