c - 解决 Timus Nr#1027 问题的最佳数据结构选择是什么？

Question

有人可以告诉我解决问题的最佳数据结构选择是什么吗@http://acm.timus.ru/problem.aspx?space=1&num=1027。

复制到这里供引用。

问题

A text of a correct D++ program contains a symbol part, arithmetic expressions and comments. Comments may appear everywhere and may contain any symbols. A comment is always opened by a pair of symbols (* and is closed by a pair of symbols * ) Each comment must be closed. An arithmetic expression in D++ is always opened by "(", is closed by ")" and may contain only symbols "=+-/0123456789)(" and "end of line" symbols. An arithmetic expression can't start with a pair of symbols "(". You may run across embedded brackets in an arithmetic expression. In this case these brackets are to be balanced. It means that "((1)))" as well as "(23))((+)" are not correct arithmetic expressions. An arithmetic expression is correct if and only if brackets placed correctly. At last, all the rest of the program text (the result of rejection of all comments and arithmetic expressions from the initial text of the program) may contain every symbol excluding "(" and ")". We would like to especially notice that the spaces are possible anywhere in a text of a program except when appearing in arithmetic expressions.

散列有用吗？

我的做法如下(还有一些bug，重点关注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

散列？否。网络搜索提示:这是上下文无关语法。