Correttore online – Facili
Una sequenza di parentesi tonde ( e ) si definisce ben formata nel modo seguente, come avviene nelle espressioni aritmetiche:
- una sequenza vuota è ben formata;
- se A e B sono sequenze ben formate, anche (A) e AB sono sequenze ben formate;
- ogni altra sequenza di parentesi non è ben formata.
Si chiede di verificare se una sequenza parentesi tonde è ben formata.
Per esempio, ()(()()) è una sequenza ben formata perché A=() e B=(()()) lo sono induttivamente in accordo alle regole suddette: nel primo caso vale A=(A1) dove A1 è vuota; nel secondo, vale B=(A2) dove A2=A3B1, con A3=B1=().
Invece, )( e (()(() non sono ben formate perché sono non vuote ma la regola 2 non può essere applicata.
Scrivere un programma che riceve una sequenza parentesi tonde e stabilisce se è ben formata o meno.
Dati di input
Il file input.txt è composto da un’unica riga contenente una sequenza di parentesi tonde, di lunghezza non nulla e comunque non superiore a 2000.
Dati di output
Il file output.txt è composto da una sola riga contenente l’indicazione CORRECT se la sequenza è ben formata, oppure INCORRECT altrimenti.
Esempi di input/output
input.txt output.txt (((()())())) CORRECT ()())(() INCORRECT Autore/i: A.S. Stankevich, ACM ICPC Team St. Petersburg State University of Information technology, Mechanics and Optics.
/*
www.valcon.it
OII - Esercizi facili - Le parentesi
*/
#include
#include
#include
using namespace std;
int main()
{
ifstream fin ( "input.txt");
ofstream fout("output.txt");
string s;
int n,pareggio,p;
fin >> s;
n=s.length();
pareggio=0;
p=0;
while(pareggio >= 0 && p < n)
{
if(s[p] == '(') pareggio++;
else if(s[p] == ')') pareggio--;
p++;
}
if(pareggio == 0) fout << "CORRECT";
else fout << "INCORRECT";
return 0;
}