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!