What’s wrong with the c-code?

Question

The task:

Pedrinho and Zezinho need to study solving mathematical expressions for a test they will do. For this, they want to solve many exercises before the test. As they know how to program, so they decided to make a generator of mathematical expressions.

The expression generator they created works in two phases.
In the first phase a string containing only the characters is generated '{', '[', '(', '}', ']' e ')'.
In the second phase, the generator adds the numbers and operators in the structure created in the first phase. A character string is said to be well defined (or valid) if it meets the following properties:

• It is an empty string (contains no character).
• It consists of a well-defined chain wrapped in parentheses, brackets or keys. Therefore, if the string S is well defined, then the strings (S), [S] and {S} are also well defined.
• It is formed by concatenating two well-defined strings. Therefore, if the strings X and Y are well-defined, the string XY is well-defined.

After Pedrinho and Zezinho generated some mathematical expressions, they realized that there was some error in the first phase of the generator. Some chains were not well defined. They want to start solving the expressions as soon as possible, and knowing that you are a great programmer (and participate in OBI) have decided to ask you to write a program that given several generated strings in the first phase, determine which ones are well defined and which ones are not.

---

Input example:

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

Respective exit:

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

The code I tried to implement:

#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;
}

I’m learning to use strings and pointers. With this code, the answer of the output is always N and I’m not identifying why, will anyone help me to solve this problem?

Answer 1

The code presented although quite close to responding correctly, has 3 problems:

• j < sizeof(exp) that is to say j < 3000000 will lead to what *p is accessing to potentially uninitialized values and even out of the area ==> possible Segmentation faults. I suggested: j < strlen(exp[i])

• within the second for missing reboot vector[] zeroed.

• the algorithm although almost perfect, will pass inputs as ([)]

(but my other answer is more interesting than this)

Answer 2

Perl is almost C

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

Update: explanation

The problem posed is interesting. Just for asking "where is my mistake?" (I tried to give a direct reply on my other answer).

The above code presents an approach different; pompously would call it programming oriented to regular expression.

The algorithm is simple:

• if we successively remove all the (), {} or [] (contiguous) and we have nothing so it is well formed.

Parallelizing with Perl (to explain the code):

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"     ⎪

This algorithm, and this approach is applicable in all that is language.

Answer 3

From the conditions of your code, I can tell you’re just counting the symbols, and printing S|N according to the quantity within vetor.

You should stack the character inside p and pop when I find the person responsible for closing it.

The example I’m sending is a little different from your code, but it’s banging with the inputs and outputs.

#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");

    }

}

Answer 4

Sorry again, but I liked this problem! and I can’t resist to propose yet another solution with another alternative algorithmic path: grammars!

Being the statement of the problem that is intended to be solved in the form

...determine which [of the sentences] are well defined and which are not,

nothing more natural than to write a grammar to define the "valid sentences" and use a grammatical recognizer to do so. This is a C problem I propose to use Yacc/Bison since it generates 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
 |
 ;
%%

Thereafter:

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

or to facilitate debug:

$ paste exemplo <(./f < exemplo)