Каков наилучший выбор структуры данных для решения Timus Nr # 1027?

Question

Может ли кто-нибудь сказать мне, что лучший выбор структуры данных для решения проблемы @http://acm.timus.ru/problem.aspx?space=1&num=1027.

Скопировано здесь для справки.

Проблема

Текст правильного D ++ программа содержит символ часть, арифметическая выражения и комментарии. Комментарии могут появляться повсюду и могут содержать . Комментарий всегда открывается парой символов (* и закрывается парой символов *). Каждый комментарий должен быть закрыт. Арифметическое выражение в D ++ всегда открывается «(», « закрыто«) »и может содержать только символы« = + - /) («и « символы конца строки ». Арифметическое выражение не может начните с пары символов « » ( «Вы можете использовать встроенные скобки в арифметическом выражении . В этом случае эти скобки должны быть сбалансированы. Это означает, что« ((1))) », а также« (23)) ((+) "неверны арифметические выражения. Арифметическое выражение является правильным, если и , только если скобки установлены правильно. Наконец, весь остальной текст программы (результат отказа от всех комментариев и арифметические выражения из исходного текста программы) могут содержать каждый символ исключая "(" и ")". Мы хотели бы особо отметить, что пространства возможны в любом месте текста программы, кроме случаев, когда появляется в арифметических выражениях.

Будет ли хеширование полезным?

Мой подход, как показано ниже (все еще есть некоторые ошибки, сосредоточиться на части DS)

 #include <stdio.h> 

     /* enable to get debug print statements */ 
     #define DEBUG_ENABLE 0 
     #define INSUFFICIENT_BUFFER -1 
     #define BUFSIZE 20 

     char buf[BUFSIZE];/*buffer for ungetch*/ 
     int bufp=0;/*next free position in buf*/ 

     /*get a(possibly pushed-back)character*/ 
     int mygetch(FILE *infile) 
     { 
      return(bufp>0)? (buf[--bufp]): (getc(infile)); 
     } 
     /*push a character back on input*/ 
     int ungetch(char c) 
     { 
      if(bufp >= BUFSIZE) 
      { 
       printf("ungetch:too many characters - increase the stack buffer size\n"); 
       return INSUFFICIENT_BUFFER; 
      } 
      else 
      { 
       buf[bufp++]=c; 
       return 0; 
      } 
     } 


     enum CharType 
     { 
      isAlphabet=0, 
      isNumber, 
      isSpace, 
      isNewline, 
      isOperator, 
      isOpeningBrace, 
      isClosingBrace, 
      isStar, 
      isOther 
     }; 

     enum 
     { 
      False=0, 
      True 
     }; 

     /* return different codes for different types of input characters*/ 
     int getCharType(char ch) 
     { 
      if((ch>='A'&&ch<='Z') || (ch>='a'&&ch<='z')) 
      { 
       return isAlphabet; 
      } 
      else if(ch=='+'||ch=='-'||ch=='/'||ch=='=') 
      { 
       return isOperator; 
      } 
      else if(ch>='0'&& ch<='9') 
      { 
       return isNumber; 
      } 
      else if(ch=='*') 
      { 
       return isStar; 
      } 
      else if(ch=='(') 
      { 
       return isOpeningBrace; 
      } 
      else if(ch==')') 
      { 
       return isClosingBrace; 
      } 
      else if(ch==' ') 
      { 
       return isSpace; 
      } 
      else 
      { 
       return isOther; 
      } 
     } 

     int parseInputFile(FILE *infile) 
     { 
      int ArthExpScanning = 0; 
      int CmmntScanning = False; 
      int ch,chtmp; 

      while((ch=mygetch(infile))!=EOF) 
      { 
     #if DEBUG_ENABLE 
       printf("%c",ch); 
     #endif /*DEBUG_ENABLE*/ 
       switch(getCharType(ch)) 
       { 
       /*Arithmetic Expression or possibly comment starts here*/ 
       case isOpeningBrace : 
        if((chtmp=mygetch(infile))!=EOF) 
        { 
        if(getCharType(chtmp)== isStar) 
        { 
         CmmntScanning = True; 
     #if DEBUG_ENABLE 
         printf("\nCmmnt Scanning = True\n"); 
     #endif /*DEBUG_ENABLE*/ 
        } 
        else if (CmmntScanning == False) 
        { 
         ArthExpScanning += 1; 
     #if DEBUG_ENABLE 
         printf("\nArthExpScanning = %d\n",ArthExpScanning); 
     #endif /*DEBUG_ENABLE*/ 
         if(ungetch(chtmp) == INSUFFICIENT_BUFFER) 
         { 
          return (0); 
         } 
        } 
        } 
        break; 
        /*Arithmetic Expression possibly closes here */ 
       case isClosingBrace : 
        if(CmmntScanning == False) 
        { 
         ArthExpScanning -= 1; 
     #if DEBUG_ENABLE 
         printf("\nArthExpScanning = %d\n",ArthExpScanning); 
     #endif /*DEBUG_ENABLE*/ 
        } 
     #if DEBUG_ENABLE 
        if(ArthExpScanning < 0) 
        { 
         printf("\nerror here!!\n"); 
        } 
     #endif /*DEBUG_ENABLE*/ 
        break; 
       case isStar : 
        if((chtmp=mygetch(infile))!=EOF) 
        { 
         if((getCharType(chtmp)== isClosingBrace) && (CmmntScanning == True)) 
        { 
         CmmntScanning = False; 
     #if DEBUG_ENABLE 
         printf("\nCmmnt Scanning = False\n"); 
     #endif /*DEBUG_ENABLE*/ 
        } 
        else 
        { 
         if(ungetch(chtmp) == INSUFFICIENT_BUFFER) 
         { 
          return (0); 
         } 
        } 
        } 
        break; 

       case isSpace : 
        if((CmmntScanning == False) && (ArthExpScanning != 0)) 
        { 
         /* Space not allowed while scanning arith exp */ 
     #if DEBUG_ENABLE 
         printf("NO \n"); 
     #endif /*DEBUG_ENABLE*/ 
         return 0; 
        } 
        break; 

       case isAlphabet : 
       case isOperator : 
       case isNumber : 
       case isNewline : 
       default: 
        break; 
       } 
      } 

      if((ArthExpScanning == 0) && (CmmntScanning == False)) 
      { 
       /* if there are no open braces and comments left after parsing the entire 
       file return success*/ 
       return 1; 
      } 
      else 
      { 
       return 0; 
      } 
     } 


     int main(int argc,char *argv[]) 
     { 
      FILE *infile; 

      if(argc != 2) 
      { 
       printf("Correct usage is : D++ExpParser inputfilename\n"); 
       return (-1); 
      } 
      if((infile = fopen(argv[1],"r")) == NULL) 
      { 
       printf("Not able to open file : %f\n",argv[1]); 
       return (-2); 
      } 
      if(parseInputFile(infile)) 
      { 
      printf("YES\n"); 
      } 
      else 
      { 
      printf("NO\n"); 
      } 

      fclose(infile); 
     } 

Answer 1

хэширования? Нет. Подсказка для вашего веб-поиска: это контекстная грамматика.