Espressione di parentesi

di

Olimpiadi Italiane a Squadre

Giorgio ha scritto un programma contenente una serie di espressioni molto elaborate, formate ciascuna da un gran numero di parentesi di tutti i tipi, e cioè:

  • angolate: ’<’ e ’>’
  • tonde: ’(’ e ’)’
  • quadrate: ’[’ e ’]’
  • graffe: ’{’ e ’}’

Purtroppo, quando ha provato ad eseguirlo, il compilatore gli ha detto che c’è un errore senza nemmeno dirgli in quale espressione si trova!
Aiutalo controllando quali espressioni sono ben formate e quali no.

Dati di input

Il file input.txt è composto da due righe.

  • La prima riga contiene l’unico intero N.
  • La seconda riga contiene la stringa E.

Dati di output

Il file output.txt è composto da un’unica riga contenente un unica parola, la risposta a questo problema.

Assunzioni

  • 1 ≤ N ≤ 10000
  • Ei è uno tra i caratteri ’{[(<>)]}’.

Esempi di input/output

input.txt output.txt
4
([)]		 malformata
5
<({})		 malformata
12
()([]{(<>)})		 corretta
20
{(<><>){{()[<>]<>}}}
 corretta

Utilizzo una seconda stringa

/*
    www.valcon.it
    Olimpiadi Italiane a Squadre - Espressione di parentesi
*/

#include
#include
#include
using namespace std;

int main() 
{		
    ifstream fin ( "input.txt");
    ofstream fout("output.txt");
	int      N;
    string   E, E2;    

    fin >> N;
	fin >> E;   
	E2.reserve(E.length());
    int pos,
	    pos2=-1;
	for(pos=0; pos < N; pos++)	
	{
		char p=E[pos];

		     if(p == '(' || p == '[' || p == '{' || p == '<') { E2[++pos2]=p;  }
	    else if(p == ')' && pos2 >= 0 && E2[pos2] == '(')     { pos2--;        }	    
	    else if(p == ']' && pos2 >= 0 && E2[pos2] == '[')     { pos2--;        }	    
	    else if(p == '}' && pos2 >= 0 && E2[pos2] == '{')     { pos2--;        }	    
	    else if(p == '>' && pos2 >= 0 && E2[pos2] == '<')     { pos2--;        }	    
	    else                                                  { pos=-1; break; }
	}
	if(pos==N) 
	    fout << "corretta";
	else
	    fout << "malformata";    
    return 0;
}

Utilizzo una pila (stack)

/*
     www.valcon.it
     Olimpiadi Italiane a Squadre - Espressione di parentesi
*/

#include 
#include 
#include 
#include 
using namespace std;

int main() 
{		
    ifstream    fin ( "input.txt");
    ofstream    fout("output.txt");
	int         N;
    string      E;
	stack s; 
    char        p1,p2;
	int         pos;
	
    fin >> N;
	fin >> E;   
    for(pos=0; pos < N; pos++)
	{
		p1=E[pos];
		if(p1=='(' || p1=='[' || p1=='{' || p1=='<') 
			s.push(p1);
	    else if(s.empty())
	    	break;
		else
		{
			p2=s.top();
			s.pop();
			if(p1==')' && p2 !='(' || p1==']' && p2 !='[' || p1=='}' && p2 !='{' || p1=='<' && p2 !='>')
				break;
	    }
	}
	if(pos==N && s.empty()) 
		fout << "corretta";
	else
	    fout << "malformata";    
    return 0;
}

Lascia un commento