c - 递归解析 - 括号

Question

有人能给我一些关于这个问题的提示吗:仅当表达式包含正确闭合的圆括号和大括号并且没有其他字符(甚至空格)时，它才是正确的。例如，() ({} () ({})) 是正确的表达式，而 ({)} 不是正确的表达式或 {} ({}))。空表达式(不包含任何字符)是正确的。给定一个字符串表达式，确定表达式是否正确，如果正确，则确定最大嵌套级别。嵌套括号的最大层数是嵌套括号的最大层数。

例子{}({}){{(({}))}}答案:5

{}({})) -1(因为表达式不正确)

这就是我到目前为止所做的。

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

Answer 1

首先，将您的问题视为形式语法会有所帮助。

S = The Language you are testing for

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

由于这个语法只有一个符号(S)，所以你只需要一种解析方法。

下面的代码是不完整的，但希望它能理解这个想法。

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