当前位置:   article > 正文

括号匹配算法

括号匹配算法

题目:有一段字符串,包含"("和")"、"["和"]"、"{"和"}"中的一种或者多种,这三种括号出现次序不定,可随意嵌套。编写代码判断三种括号是否正确匹配。


思路一(栈的思想)括号匹配是运用栈的经典思想。算法中设置一个空栈,每次读入一个括号,若是左括号,则压入栈中,等到对应的右括号压栈,若是右括号,能使置于栈顶的最急迫的期待得以消解,此时将栈顶的左括号弹出,或者是不匹配的情况,判断为不匹配。待算法结束时,栈中应该为空,判断为匹配。


前提说明:

顺序表类型定义如下:

typedef struct 

{
    ElemType *elem;
    int       length;
    int       listsize;
} SqList;  // 顺序表

Stack是一个已实现的栈。

可使用的相关类型和函数:
typedef char SElemType; // 栈Stack的元素类型
Status InitStack(Stack &s);
Status Push(Stack &s, SElemType e);
Status Pop(Stack &s, SElemType &e);
Status StackEmpty(Stack s);
Status GetTop(Stack s, SElemType &e);

主要函数代码:

 1 Status MatchCheck(SqList exp)
 2 /* 顺序表exp表示表达式;                        */
 3 /* 若exp中的括号配对,则返回TRUE,否则返回FALSE */
 4 {
 5     Stack s;
 6     char e;
 7 
 8     //逐个读入括号
 9     for(int i=0;i<exp.length;i++)
10     {
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小惠珠哦/article/detail/880356
推荐阅读
相关标签
  

闽ICP备14008679号