C funções para manipulação de pilha

Paulinha Marcelino · 9 de novembro de 2019

Utilizando as funções primitivas para manipulação de pilha, escreva um programa em C para determinar se uma string de caracteres de entrada é da forma: xCy

onde x é uma string consistindo nas letras 'A' e 'B', e y é o inverso de x (isto é, se x = "ABABBA", y deve equivaler a "ABBABA"). Em cada ponto, você só poderá ler o próximo caractere da string.

Alguem pode me falar como fica o código dessa função??

Mayrinck Bernardo · 10 de novembro de 2019

olha esse exemplo talvez te ajude

 

#include <stdio.h> 
#include <stdlib.h> 

typedef struct cel { 
   char conteudo; 
   struct cel *prox; 
} celula; 

void empilha(char c, celula *topo) { 
   celula *nova; 
   nova = malloc( sizeof (celula)); 
   nova->conteudo = c; 
   nova->prox = topo->prox; 
   topo->prox = nova; 
} 

char desempilha(celula *topo) { 
   char c; 
   celula *pt; 
   pt = topo->prox; 
   c = pt->conteudo; 
   topo->prox = pt->prox; 
   free(pt); 
   return c; 
} 

int verifica(char *str, celula *topo) { 
   for (i=0; str != 'C'; i++) 
      empilha(str, topo); 
   for (i=0; str != '\0'; i++) 
      if (desempilha(topo) != str) 
         return 1; 
   return (topo->prox == NULL); 
} 

int main() { 
   char str[255]; 
   int i; 
   celula cabeca; 
   celula *topo; 
   topo = &cabeca; 
   topo->prox = NULL; 
   printf("Informe a string: "); 
   gets(str); 
   if (verifica(str, topo) == 0) 
      printf("%s é da forma xCy\n", str); 
   else 
      printf("%s não é da forma xCy\n", str); 
   return 0; 
}

brund321 · 10 de novembro de 2019

@Paulinha Marcelino Oi, tudo bem? Pelo que eu entendi a string seria por exemplo: "ABABBACABBABA", correto? Você sabe o que é uma pilha? Se sim desenvolver esse algoritmo é bem simples você vai jogando todos os caracteres da string em uma pilha até chegar no "C" que seria o divisor da parte x e y. Então você vai no próximo caractere e começa a comparar com o último elemento da pilha caso ele seja igual você deleta e vai para o próximo caractere da string.... caso não seja você retorna "não", porque a string y não será o inverso da x, caso a pilha ficar vazia retorne "sim", isso quer dizer que a string y é o inverso de x.

arfneto · 10 de novembro de 2019

19 horas atrás, Paulinha Marcelino disse:

Utilizando as funções primitivas para manipulação de pilha, escreva um programa em C para determinar se uma string de caracteres de entrada é da forma: xCy

onde x é uma string consistindo nas letras 'A' e 'B', e y é o inverso de x (isto é, se x = "ABABBA", y deve equivaler a "ABBABA"). Em cada ponto, você só poderá ler o próximo caractere da string.

Alguem pode me falar como fica o código dessa função??

Como está claro aí, você deve partir das tais funções primitivas para manipulação da pilha. Então você precisa saber o que é isso, basicamente empilha/desempilha, numa analogia óbvia a qualquer pilha de coisas. Você tem que resolver isso considerando pop() / push() para tirar ou por algo nessa tal pilha. Esses são os nomes já consagrados para essas funções

Como veria por exemplo ao empilhar pratos numerados, as coisas saem da pilha na ordem inversa àquela em que entraram. Last In First Out ou LIFO é como costuma estar nos livros. Um exemplo real clássico seria a pilha de pratos no restaurante self-service: pegar sempre o prato de cima costuma ser a realidade.

é lógico que você não pode resolver esse exercício sem usar o conceito de pilha

Da pilha para a string xCy

Como deve ter imaginado, você deve empilhar a string toda e desempilhar e fazer algo pra dizer se a string de entrada é dessa forma. A string C pode ser "" vazia, então "ABCCBA" satisfaz seu critério. As strings x e y NÃO podem ser "" --- vazias --- por que aí teria que retornar verdadeiro para qualquer string C, é claro. Mas podem ter uma letra só, como "ACOISA" onde x e y seriam "A"

Usando duas pilhas

Uma solução ingênua e até divertida seria colocar a string toda numa pilha. Ex "123ABCD321" e depois desempilhar e empilhar em outra. É óbvio que a outra ia ficar "123DCBA321" simplesmente invertida. Pense na pilha de pratos ou use uns pedaços de papel com as letras e empilhe e desempilhe para uma outra pilha: SIM, eles vão ficar ao contrário.

Então na primeira pilha você tem x e na segunda pilha você tem y que é x ao contrário? Sim. Isso resolve o exercício? Sim

Veja:

Para a string "123ABCD321"
123ABCD321
123DCBA321    da forma xCy para x = "123"

Para a string "AZUL"
AZUL
LUZA    não é da forma xCy

Para a string "ABCCBA"
ABCCBA
ABCCBA    da forma xCy para x = "ABC"

Então basta ir vendo letra a letra. É um único loop para varrer as strings, e é bem óbvio que uma string tem o mesmo comprimento do inverso dela e esse será o final do loop.

Se a primeira letra for diferente já era: não é do formato xCy.
Se for igual continua comparando no loop e montando sua string x.

No primeiro exemplo vai ver que "123" atende mas "123A" é diferente de "123D" então a string é do formato xCy para x = "123".

Como programar isso?

Claro que tem que escrever as rotinas para a pilha, push() e pop(). Pode usar qualquer coisa, como um vetor com as letras e um ponteiro para cada pilha.

Bem simples:

empilhar: avança o ponteiro e coloca no vetor a letra
desempilhar: retorna a letra que está no topo e diminui o ponteiro

Depois empilha a string todinha na pilha A, um loop.

Depois desempilha a pilha A todinha e vai empilhando na pilha B que vai ficar claro ao contrário. Um loop

Depois compara as letras uma a uma. Um loop.

E já era.

Exemplo

"123A1"

A pilha A vai ficar 1 | 2 | 3 | A | 1 com o ponteiro no final no último 1

Tirando um a um e colocando em B vem 1,A,3,2 e 1 para B

A pilha B vai ficar 1 | A | 3 | 2 | 1

A 1 | 2 | 3 | A | 1

B 1 | A | 3 | 2 | 1

e comparando temos 1 = 1 mas 2 != A então a string é da forma xCy para x = "1"

Ansi C · 11 de novembro de 2019

@Paulinha Marcelino

Em 09/11/2019 às 21:25, brund321 disse:

Oi, tudo bem? Pelo que eu entendi a string seria por exemplo: "ABABBACABBABA", correto?

Você sabe o que é uma pilha? Se sim desenvolver esse algoritmo é bem simples você vai jogando todos os caracteres da string em uma pilha até chegar no "C" que seria o divisor da parte x e y.

^[1]Então você vai no próximo caractere e começa a comparar com o último elemento da pilha caso ele seja igual você deleta e vai para o próximo caractere da string.... caso não seja você retorna "não", porque a string y não será o inverso da x, caso a pilha ficar vazia retorne "sim", isso quer dizer que a string y é o inverso de x.

[1] Isso já resolve a parte lógica do programa!

Em 09/11/2019 às 15:33, Paulinha Marcelino disse:

Utilizando ^[2]as funções primitivas para manipulação de pilha [...] ^[3]Alguém pode me falar como fica o código dessa função?

[2] São suas operações, aqui um exemplo: https://www.cos.ufrj.br/~rfarias/cos121/pilhas.html

[3] Acredito que estudou, foi para a aula, dedicou tempo lendo os assuntos e esse é agora o seu exercício. Se alguém mostra como fica sua resposta que sentido há nisso tudo para você?

Obrigado.