• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

ZNez

[DUVIDA] Exercicio sobre Pilhas

24 mensagens neste tópico

Boas, tava por aqui a resolver uns exercicios quando me surgiu mais uma duvida.

Exercicio:

É dado um ficheiro de texto funcao.txt que contém o código de uma função escrita na linguagem C. Implemente um programa que leia o texto desse ficheiro e verifique a sua validade sintáctica tendo somente em conta as restrições associadas à utilização dos caracteres {,(,[,],) e } na linguagem C. Por outras palavras, o programa deverá verificar se os parêntesis se encontram equilibrados: para cada abertura há um fecho; entre cada par abertura/fecho não pode haver um parêntesis isolado, só outros pares abertura/fecho. Pretende-se que o programa recorra a uma Pilha para a verificação da correcção sintática.

O seu programa deverá no final imprimir uma mensagem para a consola indicando se se trata de uma função sintacticamente válida ou não. Declare os tipos de dados que utilizar.

A minha duvida esta no que escrevi a negrito.

O que e pretendido que coloque na pilha?

Ainda nao o comecei a fazer, pois gosto primeiro de ter uma ideia total de como planeio de fazer o codigo. e esse ponto do codigo, esta-me a dar as voltas a cabeca.

qualquer ajuda, obrigado :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A meu ver, colocas na pilha os caracteres {, (, [, ], ), } conforme vais lendo o texto.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

sempre que encontro um desses caracteres coloco-o na pilha.

no fim de lido o ficheiro... leio a pilha e verifico s se encontram sempre os pares de carecteres.

e assim?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sim. Tens de ter atenção que numa pilha, só se insere/remove elementos da sua cabeça/topo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

ok. obrigado.

vou tentar fazer o exercicio e amnha... ou melhor hoje digo algo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu fazia de outra maneira: metia só os caracteres {, ( e [, e de cada vez que encontrasse os correspondentes, retirava o 1º da pilha e via se correspondia. No fim, se a pilha estivesse vazia, é porque a função era válida.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A sugestão do The Dark faz sentido... Senão para quê usar uma pilha?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Para empilhar. xD

Já tinha pensado na hipótese do TheDark mas não estava a chegar lá.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Bem, ja comecei a fazer o codigo, mas ando por aqui com outra duvida, que alias so reparei na altura da compilacao.

O codigo funciona se os parentesis estiverem seguidos... agora para codigo em que seja algo do genero {()} ele diz que esta errado.

Têm alguma sugestao?

Aqui esta a minha tentativa:

[code]void input_stack(STACK_TYPE *stack)
{
    FILE *fp;
    char ch;
    
    if((fp=fopen("funcao.txt","r")) == NULL)
    {
        puts("Impossivel abrir ficheiro");
        exit(1);
    }
    while (((ch=fgetc(fp)) != EOF) && (full_stack(stack) == 0))
    {
        if ((ch == '{') || (ch == '}') || (ch == '(') || (ch == ')') || (ch == '[') || (ch == ']'))
                 push(stack,ch);
    }
    
}

void output_stack(STACK_TYPE *stack, STACK_TYPE * aux_stack)
{
    int out, out_par, par_enc = 1;
    
    while (empty_stack(stack) == 0)
        push(aux_stack,pop(stack));
    
    while(par_enc == 1)
    {
        if (empty_stack(aux_stack) == 1)
        {
            puts("PILHA VAZIA");
            par_enc=0;
        }
        
        out = pop(aux_stack);
        out_par = pop(aux_stack);
        
        if((out=='{') && (out_par=='}'))
            puts("MATCH FOR {}");
        else if((out=='(') && (out_par==')'))
            puts("MATCH FOR ()");
        else if((out=='[') && (out_par==']'))
            puts("MATCH FOR []");
        else
        {
            printf("Par nao encontrado - FUNCAO SINTATICAMENTE INVALIDA");
            par_enc=0;
        }
    }
}

[/code]

Edit: segui a ideia do TheDark que foi a q me pareceu mais simples.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

É de mim, ou estás a meter tudo na stack (os que abrem e os que fecham)?

Era só para meteres os que abrem, e quando aparecer um fecho, retiras o elemento do topo, e comparas a ver se são iguais.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

estou com umas dificuldades em fazer isso. a pilha so me permite aceder ao ultimo elemento adicionado. como e q posso fazer essa comparacao?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

... Aparece-te um caracter de fecho que está na variável ch, fazes pop à pilha e ficas a saber qual o caracter que estava no topo. Se forem iguais ok, se forem diferentes: erro...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tao fazes o pop e comparas se for diferente retornas erro, se for igual, continuas...

EDIT: pois isso que o pedro disse  :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mas nao surge um problema?

Imaginemos que temos o seguinte codigo:

main()
{
    int var;
    char var2;
    puts("Qualquer coisa no ecra");
    gets(var2);
}

na pilha vai ficar: } ) ( ) ( } ) (  entao, logo a primeira comparacao falha.

ou estou para aqui a fazer uma grande confusão...?  ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

na pilha nunca pode ficar isso porque cada vez que fazes uma comparaçao e der correcto removes o gajo do topo:

pilha :

pilha : (

pilha : {

pilha : {(

pilha : {

pilha : {(

pilha : {

pilha : vazia!

Sucesso

É assim que tem de funcionar a tua pilha!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mais explicitamente:

[table]

[/table]

Sucesso

Outro Exemplo:

[table]

[/table]
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

mas na pilha so posso aceder ao ultimo elemento adicionado. como e que posso comparar com os outros valores?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Quando lês um caracter de fecho, seja }, ) ou ], retiras o 1º elemento da pilha e comparas. A ideia é comparares enquanto estás a ler, e não leres tudo e depois comparares.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

E so presisamente a esse é que precisas de comparar, garantindo assim o emparelhamento, garantindo assim que cada vez q um parentsis fecha houve outro que ja foi aberto, que forma o respectivo par.

Aconcelho-te a testares com um exemplo simples e com uma situaçao de sucesso e erro, mas em papel para perceberes como funciona o algoritmo.

E tal como o Dark disse a comparaçao é sempre feita em "tempo de execuçao".

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ja consegui fazer a comparacao com o texto. Mas agora detectei um bug...

Se o ultimo elemento da pilha não tiver o seu complementar no texto, o programa não detecta o erro...

        int nao_enc = 1;

        out = pop(stack);
        printf("OUT: %c\n",out);
        
        while ((ch = getc(fp)) != EOF)
        {
            printf("ch: %c\n",ch);
            if((out == '}') && (ch == '{'))
            {
                puts("CORRESPONDENCIA: }");
                out = pop(stack);
                printf("OUT: %c\n",out);
                nao_enc = 0;
            }
            else if((out == '{') && (ch == '}'))
            {
                puts("CORRESPONDENCIA: {");
                out = pop(stack);
                printf("OUT: %c\n",out);
                nao_enc = 0;
            }
            if (empty_stack(stack) == 1)
                puts("PILHA VAZIA");
        }

        if (nao_enc == 1)
        {
            printf("FUNCAO INVALIDA\nValor: %c na stack",out);
        }
}

O texto que usei para testar foi:

main

{

    destroy_stack{&stack;

}

Ficando na pilha:

}

{

{

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ganda confusao de codigo meu!

PSEUDO:

int falha = false;

while ((ch = getc(fp)) != EOF && !fallha) {

if (parentsis abrir) { push(ch); }

else if (ch = ')' ) { if (pop() != '(' ) falha = true}

else if  ....

}

if (!falha && stack_vazia()) printf( "SUcesso")

else "Erro"

-----------------

Batido as 3 pancadas mas é mais o menos isso, senao percebes alguma coisa depois explico

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora