找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
查看: 2663|回复: 0
收起左侧

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

[复制链接]
ID:390214 发表于 2018-8-27 17:35 | 显示全部楼层 |阅读模式
    括号匹配检测:例如{ 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]

评分

参与人数 1黑币 +50 收起 理由
admin + 50 共享资料的黑币奖励!

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

手机版|小黑屋|51黑电子论坛 |51黑电子论坛6群 QQ 管理员QQ:125739409;技术交流QQ群281945664

Powered by 单片机教程网

快速回复 返回顶部 返回列表