4

A tarefa:

Pedrinho e Zezinho estão precisando estudar resolução de expressões matemáticas para uma prova que irão fazer. Para isso, eles querem resolver muitos exercícios antes da prova. Como sabem programar, então decidiram fazer um gerador de expressões matemáticas.

O gerador de expressões que eles criaram funciona em duas fases.
Na primeira fase é gerada uma cadeia de caracteres que contém apenas os caracteres '{', '[', '(', '}', ']' e ')'.
Na segunda fase, o gerador adiciona os números e operadores na estrutura criada na primeira fase. Uma cadeia de caracteres é dita bem definida (ou válida) se atende as seguintes propriedades:

  • Ela é uma cadeia de caracteres vazia (não contém nenhum caractere).
  • Ela é formada por uma cadeia bem definida envolvida por parênteses, colchetes ou chaves. Portanto, se a cadeia S é bem definida, então as cadeias (S), [S] e {S} também são bem definidas.
  • Ela é formada pela concatenação de duas cadeias bem definidas. Logo, se as cadeias X e Y são bem definidas, a cadeia XY é bem definida.

Depois que Pedrinho e Zezinho geraram algumas expressões matemáticas, eles perceberam que havia algum erro na primeira fase do gerador. Algumas cadeias não eram bem definidas. Eles querem começar a resolver as expressões o mais rápido possível, e sabendo que você é um ótimo programador (e participa da OBI) resolveram pedir que escreva um programa que dadas várias cadeias geradas na primeira fase, determine quais delas são bem definidas e quais não são.


Exemplo de entrada:

12
()
[]
{}
(]
}{
([{}])
{}()[]
()]
{[]
(
(([{}{}()[]])(){}){}
(((((((((({([])}])))))))))

Respectiva saída:

S
S
S
N
N
S
S
N
N
N
S
N

O código que tentei implementar:

#include<stdio.h>
#include<string.h>
int main () {
    int N, i, res[10000]={0}, vetor[6]={0}, j;
    char exp[100000][30], *p;
    scanf ("%d", &N);
    for (i=0;i<N;i++){
        scanf("%s", exp[i]);
        p=exp[i];
        for(j=0;j<sizeof(exp); j++){
            if (*p=='{')vetor[0]++;
            else if (*p=='[')vetor[1]++;
            else if (*p=='(')vetor[2]++;
            else if (*p==')' && vetor[2]>vetor[3])vetor[3]++;
            else if (*p==']' && vetor[1]>vetor[4])vetor[4]++;
            else if (*p=='}' && vetor[0]>vetor[5])vetor[5]++;
            if (vetor[0]==vetor[5] && vetor[1]==vetor[4] && vetor[2]==vetor[3]) res[i]=1;
            else res[i]=0;
            p++;
        }
    }
    for (i=0;i<N;i++){
        if (res[i]) printf("S\n");
        else printf("N\n");
    }
    return 0;
}

Estou aprendendo a usar strings e ponteiros. Com esse código, a resposta da saída é sempre N e não estou identificando o porquê, será que alguém poderia me ajudar a resolver esse problema?

0

4 Respostas 4

8

O código apresentado embora bastante próximo de responder corretamente, tem 3 problemas:

  • j < sizeof(exp) ou seja j < 3000000 vai levar a que *p esteja a aceder a valores potencialmente não inicializados e até fora da área ==> possíveis segmentation faults. Sugeria: j < strlen(exp[i])

  • dentro do segundo for falta reinicializar vector[] a zeros.

  • o algoritmo embora quase perfeito, vai deixar passar entradas como ([)]

(mas a minha outra resposta é mais interessante que esta ☺)

1
  • 3
    Basta apagar a outra resposta, caso queira manter apenas uma resposta. Pode tambem juntar ambas em uma só.
    – user28595
    Commented 18/04/2016 às 18:26
4

Pelas condicionais do seu código, deu para ver que está apenas contando os símbolos, e imprimindo S|N de acordo com a quantidade dentro de vetor.

Você deveria empilhar o caractere dentro de p e desempilhar quando encontrasse o responsável por fechá-lo.

O exemplo que estou enviando está um pouco diferente do seu código, mas está batendo com as entradas e saídas.

#include <stdio.h>
#include <string.h>

int main(int argc, char **argv){
    int n_in;

    scanf("%d\n", &n_in);
    char in[n_in][512];
    char check[512];
    char res;

    bzero(in, sizeof(in)); // zera os valores de in

    int x,y;
    for(x=0; x<n_in; x++){
        scanf("%s",in[x]);
    }

    for(x=0;x<n_in;x++){
        res = 1;
        bzero(check, sizeof(check)); // zera os valores de check
        for(y=0; y<strlen(in[x]); y++){
            switch(in[x][y]){
                case '(': // quando o caracter for '(' ou '['
                case '[': // ou '{', irá empilhar o valor de
                case '{': // in[x][y] em check
                    check[strlen(check)] = in[x][y];
                    break;
                case ')':
                    if(strlen(check) && check[strlen(check)-1] == '(')
                        check[strlen(check)-1] = 0;
                    else
                        res = 0;
                    break;
                case ']':
                    if(strlen(check) && check[strlen(check)-1] == '[')
                        check[strlen(check)-1] = 0;
                    else
                        res = 0;
                    break;
                case '}':
                    if(strlen(check) && check[strlen(check)-1] == '{')
                        check[strlen(check)-1] = 0;
                    else
                        res = 0;
                    break;
            }
            if(!res)
                break;
        }
        if(res && strlen(check) == 0)
            puts("S");
        else
            puts("N");

    }

}
1
  • 1
    @JJoao, sim o código tem suas verificações, mas o que eu realmente quis dizer na primeira frase, é que o uso dos múltiplos vetores são responsáveis pelo problema. Pois a resposta final é baseada na analise das posições deles. Commented 18/04/2016 às 19:59
4

Perl é quase C 😇

perl -ne ' while( s!\(\)|\[\]|\{\}!! ){}; 
           print (/\S/ ? "N\n" : "S\n")'` ex1

Update: explicação

O problema posto é interessante. Peca apenas por só perguntar "onde está o meu erro?" (tentei dar uma resposta direta na minha outra resposta).

No código acima apresenta-se uma abordagem diferente; pomposamente chamar-lhe-ia programação orientada à expressão regular.

O algoritmo é simples:

  • se sucessivamente retirarmos todos os (), {} ou [] (contíguos) e ficarmos sem nada então está bem formada.

Paralelizando com o Perl (para explicar o código):

para linha ∈ texto                          ⎪    perl -n
 ⎧ enquanto for possível                    ⎪      while(
 ⎪  ⎩ substituir( /() ou [] ou {}/ , "")    ⎪         s/()|[]|{}//   ){}
 ⎨                                          ⎪
 ⎪ se(linha ficou vazia) → escrever "S"     ⎪      print ...
 ⎩     senão             → escrever "N"     ⎪

Este algoritmo, e esta abordagem é aplicável em tudo o que é linguagem.

0
2

Desculpem mais uma vez, mas eu gostei deste problema! e não resisto a propor mais uma solução com outro caminho algorítmico alternativo: gramáticas!

Sendo o enunciado do problema que se pretende resolver da forma

...determine quais [das frases] são bem definidas e quais não são,

nada mais natural que escrever uma gramática para definir as "frases válidas" e usar um reconhecedor gramatical para o fazer. Tratando-se de um problema C proponho o uso do yacc/bison já que gera C

%code {
  #include<stdio.h>
  void yyerror(){ }
  int yylex(){return getchar();}         // analisador léxico = getchar()
}

%%
f: f     e '\n' {printf("S\n");}  // zero ou mais expressões <CR>
 | f error '\n' {printf("N\n");}  // ...tratamento de erros
 |
 ;

e: '{' e '}' e                    // cada expressão pode ser : ....
 | '[' e ']' e
 | '(' e ')' e
 |
 ;
%%

Seguidamente:

$ bison f.y                  ## gera o ficheiro "y.tab.c"
$ cc -o f  f.tab.c -ly       ## compilar
$ ./f < exemplo              ## testar
N
S
S

ou para facilitar o debug:

$ paste exemplo <(./f < exemplo)

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

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .