1

Boa noite galera!

Estou tentando fazer um exercício da OBI de 2011. Aqui o link para ele: Exercicio OBI 2011- Expressões e encontrei alguns problemas para realiza-lo.

Em resumo, o exercício te fornece uma cadeia de caracteres: {[(}]) e você precisa dizer se estão 'balanceadas' ou não.

Exemplo de cadeias balanceadas: {},{[]}, ([{}]).

Exemplo de cadeias não balanceadas, }{, [{}}, [}.

Pensei de utilizar uma pilha que conta o numero de "[, { e (" que encontra para dar push (nesse caso, aumenta a pilha com o ultimo [, {, ou ( encontrado). E apos isso, ir comparando para ver se o restante da cadeia possui os caracteres opostos a quem está no topo da pilha. Então, se no topo estiver '{', ele procura por '}' e se achar, remove da pilha. No final, se sobrar elementos na pilha, significa que a cadeia não está balanceada.

Segue minha implementação:

Main:

int main()
{
  //Numero de instancias
  int T;
  scanf("%d", &T);

  int i;
  char* exp;

  for( i = 0; i < T; i++)
  {
      scanf("%s", exp);
      if(validaCadeia(exp) == 0)
        printf("S\n");
      else
        printf("N\n");
  }

  return(0);
}

No main, eu pego a quantidade de expressoes que o usuario quer efetuar(T), e faço um for pedindo a cadeia de caracteres e chamando a função que verifica se estão balanceados.

A função:

int validaCadeia(char* cadeia)
{
  int i = 0;

  //declara o Nó cabeça, ou topo
  /*Declaração da pilha e de suas variaveis.*/
  Pilha* p = (Pilha*)malloc(sizeof(Pilha));

  if(!p)
    return(0);

  //Inicia a pilha como vazia
  p->topo = NULL;

  while(cadeia[i] != '\0')
  {

    // Coloca na pilha caso { [ ou (
    if( cadeia[i] == '(' ||
        cadeia[i] == '[' ||
        cadeia[i] == '{')

        push(p, cadeia[i]);

    // Caso }]) ele compara pra ver se o topo é igual ao charactere
    if( cadeia[i] == ')' ||
        cadeia[i] == ']' ||
        cadeia[i] == '}')
    {

        //Se a pilha for nula e achar um }, não é balanceada
        if(p->topo == NULL)
          return(0);

      //Caso a pilha tiver elementos.
      else
          if(topo->simbolo == cadeia[i])
          pop(p);
    }

    //Incrementa cadeia[i]
    i++;
}

//Se tiver elementos no stack
if(p->tam = -1 )
  return(1);

if (p->tam > -1)
  return(0);
}

Aqui minha tento implementar minha ideia, só que o compilador acusa erro de tipo nas funções push e pop.

Push:

void push(Pilha p, char E)
{
    No* novo = (No*)malloc(sizeof(No));

    novo->simbolo = E;
    novo->prox = p->topo;
    p->topo = novo;

    p->tam += 1;
}

Pop:

void pop(Pilha p)
{
  No* aux = p->topo;
  p->topo = p->topo->prox;
  free(aux);
  p->tam -= 1;
}

E minhas structs:

typedef struct No
{
  char simbolo;
  int top;
  struct No* prox;
} No;

typedef struct pilha
{
    No* topo;
    int tam;
}Pilha;

Pelo que entendi meus erros estão relacionados a manipulação de ponteiros, se puderem apontar quais são, ficaria muito grato.

Obrigado!

0

Você deve fazer log-in para responder a esta pergunta.

Pesquise outras perguntas com a tag .