C语言利用栈的FILO特性实现括号匹配检测 -

标题: C语言利用栈的FILO特性实现括号匹配检测 [打印本页]

作者: hahajiajun 时间: 2018-8-27 17:35
标题: C语言利用栈的FILO特性实现括号匹配检测
括号匹配检测：例如{ 9 * [2（x+6) ] }，需要检测右边的 )、 ]、}是否与左边的括号匹配。

原理：把上述方程存入一个字符数组当中，存储完毕后遍历数组，当遇到左括号时就PUSH入栈；当遇到右括号时就POP出栈，比较此时的右括号与此时POP出栈的左括号是否匹配。

优化：利用栈的FILO特性（逆序）和数组（正序）可以实现：把上面的方程中的左括号都存入一个字符栈当中，右括号都存入一个字符数组当中，可以节约遍历存放方程的数组的时间。
typedef struct
{
      DataType *base, *top;
      int stacksize;
}STA;

int Match( STA *STACK, char *Str )    //定义匹配函数。char *Str 是存放方程的数组
{
      int i;
      int Marker = 1;                   //定义一个标志符
      for(i = 0;Str[ i] != '\0';i++)
      {
         switch( Str[ i] )                //跳跃性的选择可以用siwtch()函数
         {
               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为零，此时它是括号不匹配的标志
                           break;
               case '}': if( POP( &STACK ) != '{' )
                              Marker = 0;
                           break;
               case ']': if( POP( &STACK ) != '[' )
                              Marker = 0;
                           break;
               default :  break;
         }
         if( !Marker ) break;       //如果Marker有一次为0,说明已经不匹配了，下面的匹
                                          //配已经没有必要进行了，直接跳出循环节省时间
      }
      if( IsEmpty(STACK) == 1 && Marker ) //考虑在没有左括号的情况下却出现了右括号的情况
         return 1;                      //如果为1就是匹配，为0就不匹配
      else
         return 0;
}

这里还需要有一个模块思维：就是把一些很简单的功能分别用一个函数表示，把它封装起来。比如IsEmpty函数，可以都封装起来,这样功能就很简洁明了了。
IsEmpty(STA STACK )
{
      return STACK.base == STACK.top;
}[ i]

欢迎光临 (http://www.51hei.com/bbs/)