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
- include <stdlib.h>
- include <string.h>
- include <iostream>
using namespace std;
- define INTOBJ 11
- define REALOBJ 12
- define STROBJ 13
- define LISTOBJ 16
- define CELLinum xpr.inum
- define CELLrnum xpr.rnum
- define CELLstr xpr.str
- define ISint(p) ((p)->flag == INTOBJ)
- define ISreal(p) ((p)->flag == REALOBJ)
- define ISstr(p) ((p)->flag == STROBJ)
- define ISlist(p) ((p)->flag == LISTOBJ)
- define CAR(p) ((p)->xpr.pair.car)
- 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;
}