Prev Up Next
Go backward to Números aleatórios e simulações
Go up to Alguns exercícios a exemplos dados nas aulas teóricas
Go forward to Várias implementações do "stack"

"Stack" para testar a colocacao de parentesis

Nota: Uma solução mais simples consiste em contar da esquerda para a direita a diferença entre o número de parêntesis abertos e fechados. A expressão está "correcta" se esse valor é 0 no fim e nunca é nagativo durante o processo. 


 // -----------------------------------------------------------------------------
 // Usa um stack para ver se a colocacao de parentesis
 // numa formula esta' correcta
 // Nota: não era necessário usar um stack, bastava um contador de ``(''

 main(){
 #define MAX 100
   int testa(char *s);
   char s[MAX];
   printf(" ? ");
   scanf("%s",s);
   if(testa(s))
     printf("Correcto!\n");
   else
     printf("Incorrecto!\n");
 }


 int testa(char *s){
   void push(char c);
   char pop(void);
   int vazio(void);
   int i;

   for(i=0;i<strlen(s);i++){
     if(s[i]=='(')
       push(s[i]);
     else
       if(s[i]==')'){
 	if(vazio())
 	  return(0);
 	else
 	  pop();  // Valor desprezado, e' '('!
       }
   }
   return(vazio());
 }

 // Stack: IMPLEMENTACAO COM UM VECTOR
 #define MAX  100
 char stack[MAX];
 int sp=0;

 void push(char c){
   stack[sp++]=c;
 }

 char pop(void){
   sp--;
   return(stack[sp]);
 }

 // Alternativa:
 // IMPLEMENTACAO COM LISTAS LIGADAS
 struct no{
   char caracter;
   struct no * mais;
 };
 struct no * sp=NULL;

 // Exercicio: use teste de existencia de memoria suficiente
 void push(char c){
   struct no * novo = (struct no *) malloc(sizeof(struct no));
   novo->mais     = sp;
   novo->caracter = c;
   sp = novo;
 }


 // Exercicio: usar teste de vazio e libertar espaco com free
 char pop(void){
   char c = sp->caracter; // valor a retornar;
   sp = sp->mais;
   return(c);
 }
  
 int vazio(void){
   return(sp==NULL);
 }

 Resultados:
  ? 1
 Correcto!
  ? (1)
 Correcto!
  ? (())())
 Incorrecto !
  ? (()))(
 Incorrecto !
  ? (2*3+(4/5))
 Correcto!




%
Prev Up Next