Data Structures and Libraries

Pilha

Problema 1068

Descrição

Dada uma expressão qualquer com parênteses, indique se a quantidade de parênteses está correta ou não, sem levar em conta o restante da expressão. Por exemplo:

a+(b*c)-2-a está correto (a+b*(2-c)-2+a)*2 está correto

enquanto

(a*b-(2+c) está incorreto 2*(3-a)) está incorreto )3+b*(2-c)( está incorreto

O seja, todo parênteses que fecha deve ter um outro parênteses que abre correspondente e não pode haver parênteses que fecha sem um previo parenteses que abre e a quantidade total de parenteses que abre e fecha deve ser igual.

Entrada

Como entrada, haverá N expressões (1 <= N <= 10000), cada uma delas com até 1000 caracteres.

Saída

O arquivo de saída deverá ter a quantidade de linhas correspondente ao arquivo de entrada, cada uma delas contendo as palavras correct ou incorrect de acordo com as regras acima fornecidas.

Exemplo de Entrada ------ Exemplo de Saída

a+(b*c)-2-a ---------- correct

(a+b*(2-c)-2+a)*2 ---- correct

(a*b-(2+c) ----------- incorrect

2*(3-a)) ------------- incorrect

)3+b*(2-c)( ---------- incorrect

Código

1. include <stdlib.h>
2. include <string.h>
3. include <iostream>

using namespace std;

1. define INTOBJ 11
2. define REALOBJ 12
3. define STROBJ 13
4. define LISTOBJ 16
5. define CELLinum xpr.inum
6. define CELLrnum xpr.rnum
7. define CELLstr xpr.str
8. define ISint(p) ((p)->flag == INTOBJ)
9. define ISreal(p) ((p)->flag == REALOBJ)
10. define ISstr(p) ((p)->flag == STROBJ)
11. define ISlist(p) ((p)->flag == LISTOBJ)
12. define CAR(p) ((p)->xpr.pair.car)
13. define CDR(p) ((p)->xpr.pair.cdr)

typedef struct cell { int flag; union { int inum; float rnum; char *str; struct { struct cell *car; struct cell *cdr; } pair; } xpr; }*sexpr;

sexpr freshcell () { sexpr obj; obj = (sexpr) malloc(sizeof(struct cell)); return obj;}

sexpr mkstr(char *str) { sexpr obj= freshcell(); char *newstr; int len= strlen(str); newstr= (char *) malloc (len+1); strcpy(newstr, str); *(newstr+len) = 0; obj->flag= STROBJ; obj->CELLstr= newstr; return obj;}

sexpr mkrnum(float rnum) { sexpr obj= freshcell(); obj->flag= REALOBJ; obj->CELLrnum= rnum; return obj;}

sexpr mkinum(int inum) { sexpr obj= freshcell(); obj->flag= INTOBJ; obj->CELLinum = inum; return(obj);}

sexpr cons(sexpr head, sexpr tail) { sexpr obj= freshcell();

       obj->flag = LISTOBJ;

CAR(obj) = head; CDR(obj) = tail; return obj;}

int main(){ sexpr abre; int i,cont; char xpr[1000], c;

while(cin>>xpr){ abre=NULL; i=0; cont=0; while(xpr[i]!='\0'){ if(xpr[i]=='('){ abre=cons(mkinum(1),abre); } if(xpr[i]==')'){ if(abre==NULL){ cont=1; goto B; }

else{ abre=CDR(abre); } } i++; } B: if(abre==NULL&&cont==0){ cout<<"correct\n"; } else{ cout<<"incorrect\n"; } } A: return 1; }