CODEWITHSUNDEEP
cparsingrecursionbrackets
riic2000
riic2000

Reputation: 21

parsing with recursion - brackets

Could some give me a hint at this problem : An expression is correct only if it contains parentheses and braces properly closed and no other character, even space. For example, () ({} () ({})) is a correct expression, whereas ({)} is not a correct expression or {} ({})). An empty expression (which does not contain any character) is correct. Given a string expression determine if the expressions is correct and if is determine the maximum level of nesting. Maximum level of nesting parentheses is the maximum number of one another.

Examples {}({}){{(({}))}} answer : 5

{}({})) -1 (because the expression is incorrect)

That's what I've did so far.

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

FILE *fi, *fo;
int first, er;

void X();
void Y();

void S() {
    X();
    Y();
}
void X() {
    if(first=='{') {
        first=fgetc(fi);
        X();
        if(first=='}')
            first=fgetc(fi);
        else
            er=1;
        S();
    }
}
void Y() {
    if(first=='(') {
        first=fgetc(fi);
        Y();
        if(first==')')
            first=fgetc(fi);
        else
            er=1;
        S();
    }
}
int main()
{
    fi = fopen("brackets.in","r");
    fo = fopen("brackets.out","w");
    first=fgetc(fi);
    S();
    if(first!='\n')
        er=-1;
    fprintf(fo,"%d",er);
    fclose(fi);
    fclose(fo);
    return 0;
}

Upvotes: 1

Views: 1676

Answers (1)

QuestionC
QuestionC

Reputation: 10064

First off, it helps to think of your problem as a formal grammar.

S = The Language you are testing for

S->
  NUL    // Empty   
  SS     // S followed by itself.   
  [ S ]  // Case 1   
  ( S )  // Case 2   
  { S }  // Case 3

Since this grammar only has one symbol (S), you only need one parsing method.

The following code is incomplete but hopefully it gets the idea across.

char curr_char;

int main (void)
{
  curr_char = getc();
  result = parse_s();
  return 0;
}

// Parse the S pattern off input.  When this method completes, curr_char points to the character AFTER S.
// Returns recursion count or -1 on fail.
int parse_s()
{
  max_count = 0;
  while(true)
  {
    int curr_count = 0;
    switch 'curr_char':
    {
      case '[': // [
        int count = parse_s(); // S
        if (count == -1) return -1;  // The S must be valid
        if (curr_char != ']') return -1;  // ]
        curr_char = getc();  // Advance past the ]
        curr_count = count + 1;  // This expression is 1 nest greater than its contained S
      break;

      case '(':
        // XXX
      break;

      case '{':
        // XXX
      break;

      default:
        // This is either the SS (find the max of the two), the NUL case (return 0), or an error (return -1)
      break;
    }
    // In the SS case you're gonna have to loop and do something here.
  }
  return max_count;
}

Upvotes: 2

Related Questions