標(biāo)題: C語言利用棧的FILO特性實(shí)現(xiàn)括號(hào)匹配檢測(cè) [打印本頁]
作者: hahajiajun    時(shí)間: 2018-8-27 17:35
標(biāo)題: C語言利用棧的FILO特性實(shí)現(xiàn)括號(hào)匹配檢測(cè)
    括號(hào)匹配檢測(cè)：例如{ 9 * [2（x+6) ] }，需要檢測(cè)右邊的 )、 ]、}是否與左邊的括號(hào)匹配。

    原理：把上述方程存入一個(gè)字符數(shù)組當(dāng)中，存儲(chǔ)完畢后遍歷數(shù)組，當(dāng)遇到左括號(hào)時(shí)就PUSH入棧；當(dāng)遇到右括號(hào)時(shí)就POP出棧，比較此時(shí)的右括號(hào)與此時(shí)POP出棧的左括號(hào)是否匹配。

    優(yōu)化：利用棧的FILO特性（逆序）和數(shù)組（正序）可以實(shí)現(xiàn)：把上面的方程中的左括號(hào)都存入一個(gè)字符棧當(dāng)中，右括號(hào)都存入一個(gè)字符數(shù)組當(dāng)中，可以節(jié)約遍歷存放方程的數(shù)組的時(shí)間。
    typedef struct
    {
        DataType *base, *top;
        int stacksize;
    }STA;

    int Match( STA *STACK, char *Str )       //定義匹配函數(shù)。char *Str 是存放方程的數(shù)組
    {
        int i;
        int Marker = 1;                      //定義一個(gè)標(biāo)志符
        for(i = 0;Str[ i] != '\0';i++)
        {
            switch( Str[ i] )                 //跳躍性的選擇可以用siwtch()函數(shù)
            {
                   case '(': PUSH( &STACK,Str[ i] );
                            break;
                   case '{':[ i][ i][ i] PUSH( &STACK,Str[ i] );[ i]
                            break;
                   case '[': PUSH( &STACK,Str[ i] );[ i]
                            break;
                  case ')': if( POP( &STACK ) != '(' )
                                Marker = 0;  //如果Marker為零，此時(shí)它是括號(hào)不匹配的標(biāo)志
                              break;         
                   case '}': if( POP( &STACK ) != '{' )
                                Marker = 0;
                              break;
                   case ']': if( POP( &STACK ) != '[' )
                                Marker = 0;
                              break;
                   default :  break;
             }
             if( !Marker )    break;          //如果Marker有一次為0,說明已經(jīng)不匹配了，下面的匹
                                              //配已經(jīng)沒有必要進(jìn)行了，直接跳出循環(huán)節(jié)省時(shí)間
        }
        if( IsEmpty(STACK) == 1 && Marker )   //考慮在沒有左括號(hào)的情況下卻出現(xiàn)了右括號(hào)的情況
            return 1;                         //如果為1就是匹配，為0就不匹配
        else
            return 0;
    }



    這里還需要有一個(gè)模塊思維：就是把一些很簡(jiǎn)單的功能分別用一個(gè)函數(shù)表示，把它封裝起來。比如IsEmpty函數(shù)，可以都封裝起來,這樣功能就很簡(jiǎn)潔明了了。
    IsEmpty(STA STACK )
    {
        return STACK.base == STACK.top;
    }[ i]



歡迎光臨 (http://www.torrancerestoration.com/bbs/) Powered by Discuz! X3.1