wiki

Data Structures and Libraries: mudanças entre as edições

← Edição anterior
 
(3 revisões intermediárias pelo mesmo usuário não estão sendo mostradas)
Linha 37: Linha 37:


=== Código ===
=== Código ===
#include <stdlib.h>
<nowiki>#include <stdlib.h></nowiki>
#include <string.h>
#include <iostream>
using namespace std;


#define INTOBJ 11
<nowiki>#include <string.h></nowiki>
#define REALOBJ 12
 
#define STROBJ  13
<nowiki>#include <iostream></nowiki>
#define LISTOBJ 16
 
#define CELLinum xpr.inum
<nowiki>using namespace std;</nowiki>
#define CELLrnum xpr.rnum
 
#define CELLstr  xpr.str
<nowiki>#define INTOBJ 11</nowiki>
#define ISint(p) ((p)->flag == INTOBJ)
 
#define ISreal(p) ((p)->flag == REALOBJ)
<nowiki>#define REALOBJ 12</nowiki>
#define ISstr(p) ((p)->flag == STROBJ)
 
#define ISlist(p) ((p)->flag == LISTOBJ)
<nowiki>#define STROBJ  13</nowiki>
#define CAR(p)    ((p)->xpr.pair.car)
 
#define CDR(p)    ((p)->xpr.pair.cdr)
<nowiki>#define LISTOBJ 16</nowiki>
 
<nowiki>#define CELLinum xpr.inum</nowiki>
 
<nowiki>#define CELLrnum xpr.rnum</nowiki>
 
<nowiki>#define CELLstr  xpr.str</nowiki>
 
<nowiki>#define ISint(p) ((p)->flag == INTOBJ)</nowiki>
 
<nowiki>#define ISreal(p) ((p)->flag == REALOBJ)</nowiki>
 
<nowiki>#define ISstr(p) ((p)->flag == STROBJ)</nowiki>
 
<nowiki>#define ISlist(p) ((p)->flag == LISTOBJ)</nowiki>
 
<nowiki>#define CAR(p)    ((p)->xpr.pair.car)</nowiki>
 
<nowiki>#define CDR(p)    ((p)->xpr.pair.cdr)</nowiki>


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;
 
                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;
        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;
}
}
<br>
<br>


=== Observações e explicações ===
=== Observações e explicações ===

Edição atual tal como às 23h59min 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;

}


Observações e explicações

Disponível em “http://3.143.69.156/wiki/index.php?title=Data_Structures_and_Libraries&oldid=23763”