首页 > 算法 > 括号匹配问题

括号匹配问题

2013年5月19日 发表评论 阅读评论 2577次阅读    

刚起床看微博,陈利人又发了个题:

“括号匹配:给定字符串,输出括号是否匹配,例如,"()" yes;")(" no;"(abcd(e)" no;"(a)(b)" yes。要求必须用递归写,整个实现不可以出现一个循环语句。"

很多人都说用栈实现,太麻烦了吧,直接用递归自然堆栈就行了:

#include <stdio.h>
#include <string.h>
//gcc  -std=c99 bracket.c

int bracket( char *p, int count){
    //返回为0匹配,否则不匹配
    if(*p == '\0') return count ;
    else if(*p == '(') return bracket( p+1, count+1) ;
    else if(count > 0 && *p == ')') return bracket( p+1, count-1) ;
    else if(count <= 0 && *p == ')') return -1 ;
    return bracket( p+1, count);
}

int main(int argc, char* argv[]) {
    char *str = "aaa(bb(()c))";
    int tmp = bracket(str, 0) ;
    printf("bracket result:%s\n", tmp==0?"yes":"no");
    return 0 ;
}

gcc bracket.c 

./a.out
bracket result:yes

然后扩展到【(【】【】)】这种有多个单元符号的,也可以类推。

Share
分类: 算法 标签:
  1. gamer
    2013年8月3日16:21 | #1

    count 其实不用传的,一个局部变量初始化为0就行;
    最后的return bracket( p+1, count);貌似是悬空的吧?

  2. passinger
    2013年5月20日11:31 | #2

    @kulv
    呵呵,就是嘛,我想代码看上去好像也没有问题,怎么会出来一个no的结果。

  3. kulv
    2013年5月20日10:36 | #3

    @passinger
    囧···下面的结果粘贴错了,谢谢哥们了!已修正

  4. passinger
    2013年5月20日09:28 | #4

    aaa(bb(()c))的测试结果不是应该是true,吗?

  1. 本文目前尚无任何 trackbacks 和 pingbacks.

注意: 评论者允许使用'@user空格'的方式将自己的评论通知另外评论者。例如, ABC是本文的评论者之一,则使用'@ABC '(不包括单引号)将会自动将您的评论发送给ABC。使用'@all ',将会将评论发送给之前所有其它评论者。请务必注意user必须和评论者名相匹配(大小写一致)。