| Linha 37: | Linha 37: | ||
=== Código === | === Código === | ||
<nowiki> | |||
#include <stdlib.h> | #include <stdlib.h> | ||
#include <string.h> | #include <string.h> | ||
#include <iostream> | #include <iostream> | ||
using namespace std; | using namespace std; | ||
#define INTOBJ 11 | #define INTOBJ 11 | ||
#define REALOBJ 12 | #define REALOBJ 12 | ||
#define STROBJ 13 | #define STROBJ 13 | ||
#define LISTOBJ 16 | #define LISTOBJ 16 | ||
#define CELLinum xpr.inum | #define CELLinum xpr.inum | ||
#define CELLrnum xpr.rnum | #define CELLrnum xpr.rnum | ||
#define CELLstr xpr.str | #define CELLstr xpr.str | ||
#define ISint(p) ((p)->flag == INTOBJ) | #define ISint(p) ((p)->flag == INTOBJ) | ||
#define ISreal(p) ((p)->flag == REALOBJ) | #define ISreal(p) ((p)->flag == REALOBJ) | ||
#define ISstr(p) ((p)->flag == STROBJ) | #define ISstr(p) ((p)->flag == STROBJ) | ||
#define ISlist(p) ((p)->flag == LISTOBJ) | #define ISlist(p) ((p)->flag == LISTOBJ) | ||
#define CAR(p) ((p)->xpr.pair.car) | #define CAR(p) ((p)->xpr.pair.car) | ||
#define CDR(p) ((p)->xpr.pair.cdr) | #define CDR(p) ((p)->xpr.pair.cdr) | ||
typedef struct cell { | typedef struct cell { | ||
int flag; | int flag; | ||
union { | union { | ||
int inum; | int inum; | ||
float rnum; | float rnum; | ||
char *str; | char *str; | ||
struct { | struct { | ||
struct cell *car; | struct cell *car; | ||
struct cell *cdr; | struct cell *cdr; | ||
} pair; | } pair; | ||
} xpr; | } xpr; | ||
}*sexpr; | }*sexpr; | ||
sexpr freshcell () { | sexpr freshcell () { | ||
sexpr obj; | sexpr obj; | ||
obj = (sexpr) malloc(sizeof(struct cell)); | obj = (sexpr) malloc(sizeof(struct cell)); | ||
return obj;} | return obj;} | ||
sexpr mkstr(char *str) { | sexpr mkstr(char *str) { | ||
sexpr obj= freshcell(); | sexpr obj= freshcell(); | ||
char *newstr; | char *newstr; | ||
int len= strlen(str); | int len= strlen(str); | ||
newstr= (char *) malloc (len+1); | newstr= (char *) malloc (len+1); | ||
strcpy(newstr, str); | strcpy(newstr, str); | ||
*(newstr+len) = 0; | *(newstr+len) = 0; | ||
obj->flag= STROBJ; | obj->flag= STROBJ; | ||
obj->CELLstr= newstr; | obj->CELLstr= newstr; | ||
return obj;} | return obj;} | ||
sexpr mkrnum(float rnum) { | sexpr mkrnum(float rnum) { | ||
sexpr obj= freshcell(); | sexpr obj= freshcell(); | ||
obj->flag= REALOBJ; | obj->flag= REALOBJ; | ||
obj->CELLrnum= rnum; | obj->CELLrnum= rnum; | ||
return obj;} | return obj;} | ||
sexpr mkinum(int inum) { | sexpr mkinum(int inum) { | ||
sexpr obj= freshcell(); | sexpr obj= freshcell(); | ||
obj->flag= INTOBJ; | obj->flag= INTOBJ; | ||
obj->CELLinum = inum; | obj->CELLinum = inum; | ||
return(obj);} | return(obj);} | ||
sexpr cons(sexpr head, sexpr tail) { | sexpr cons(sexpr head, sexpr tail) { | ||
sexpr obj= freshcell(); | sexpr obj= freshcell(); | ||
obj->flag = LISTOBJ; | |||
CAR(obj) = head; | CAR(obj) = head; | ||
CDR(obj) = tail; | CDR(obj) = tail; | ||
return obj;} | return obj;} | ||
int main(){ | int main(){ | ||
sexpr abre; | |||
int i,cont; | sexpr abre; | ||
int i,cont; | |||
char xpr[1000], c; | char xpr[1000], c; | ||
while(cin>>xpr){ | while(cin>>xpr){ | ||
abre=NULL; | |||
i=0; | i=0; | ||
cont=0; | cont=0; | ||
while(xpr[i]!='\0'){ | while(xpr[i]!='\0'){ | ||
if(xpr[i]=='('){ | if(xpr[i]=='('){ | ||
abre=cons(mkinum(1),abre); | abre=cons(mkinum(1),abre); | ||
} | } | ||
if(xpr[i]==')'){ | if(xpr[i]==')'){ | ||
if(abre==NULL){ | if(abre==NULL){ | ||
cont=1; | cont=1; | ||
goto B; | goto B; | ||
} | } | ||
else{ | else{ | ||
abre=CDR(abre); | abre=CDR(abre); | ||
} | } | ||
} | } | ||
i++; | i++; | ||
} | } | ||
B: | B: | ||
if(abre==NULL&&cont==0){ | if(abre==NULL&&cont==0){ | ||
cout<<"correct\n"; | cout<<"correct\n"; | ||
} | } | ||
else{ | else{ | ||
cout<<"incorrect\n"; | cout<<"incorrect\n"; | ||
} | } | ||
} | } | ||
A: | A: | ||
return 1; | return 1; | ||
} | } | ||
</nowiki> | |||
<br> | <br> | ||
=== Observações e explicações === | === Observações e explicações === | ||
Edição das 22h41min de 28 de janeiro de 2014
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;
}