数据结构(3 |
您所在的位置：网站首页 › 用栈检测括号是否匹配的函数 › 数据结构(3 |
|
数据结构--用栈实现括号匹配的检验
目录括号匹配要求程序思路代码实现
目录
括号匹配要求
假设表达式中允许包含三种括号：{大括号}、[中括号]和(小括号)，其嵌套的顺序随意，即{()}、[{([][])}]、({}[])]等为正确的格式,[(])、([()、(()])、{[()]等均为不正确的格式。 输出格式： 成功匹配则输出： 匹配成功 若匹配失败（例：{[()][)}） 匹配失败 若左括号多余（例：[[[]]） 左括号多余 若右括号多余（例：[[]]]) 右括号多余 程序思路期待的急迫程度 考虑下列括号序列 { ( [ ] [ ] ) } 1 2 3 4 5 6 7 8 当计算机接受了第一个括号后,它期待着与其匹配的第八个括号的出现,然而等来的却是第二个括号,此时第一个括号“{”只能暂时靠边,而迫切等待与第二个括号相匹配的、第七个括号“)”的出现,类似地,因等来的是第三个括号“[”,其期待匹配的程度较第二个括号更急迫,则第二个括号也只能靠边,让位于第三个括号,显然第二个括号的期待急迫性高于第一个括号;在接受了第四个括号之后,第三个括号的期待得到满足,消解之后,第二个括号的期待匹配就成为当前最急迫的任务了,……,依次类推。可见,这个处理过程恰与栈的特点相吻合。由此,在算法中设置一个栈,每读入一个括号,若是右括号,则或者使置于栈顶的最急迫的期待得以消解,或者是不合法的情况;若是左括号,则作为一个新的更急迫的期待压入栈中,自然使原有的在栈中的所有未消解的期待的急迫性都降了一级。 另外,在算法的开始和结束时,栈都应该是空的。 代码实现C++实现（C语言版请联系博主） 有疑问请评论讨论 若有漏洞请不吝指出 #include #include //realloc函数头文件部分编译器不需要此行代码 using namespace std; #define ERROR 0 #define OK 1 #define E_L 2//左括号多余的情况 #define E_R 3//右括号多余的情况 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef char ElemType; typedef int Status; typedef struct { ElemType *base; ElemType *top; int stacksize; } Stack; Status InitStack(Stack &S) // 构造一个空栈S { if (!(S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)))) exit(0); // 存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; } Status Push(Stack &S, ElemType e) //入栈 { // 插入元素e为新的栈顶元素 if (S.top - S.base >= S.stacksize) // 栈满，追加存储空间 { S.base = (ElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(ElemType)); if (!S.base) exit(0); // 存储分配失败 S.top = S.base + S.stacksize; //确保S满栈的情况，top在base上方的当前栈长处 S.stacksize += STACKINCREMENT; } *(S.top)++ = e; /*或者 *S.top = e; *S.top++; */ return OK; } Status Pop(Stack &S) //出栈，移除当前栈顶元素 { if (S.top == S.base) return ERROR; S.top--; return OK; } Status StackEmpty(Stack S) //检测是否为空栈 { if (S.top == S.base) return OK; else return ERROR; } ElemType GetTop(Stack S) //返回栈顶元素 { if (S.top == S.base) return ERROR; else return *(S.top - 1); } Status Match(Stack &S, string str) { int Count_L = 0; //左括号计数器 int Count_R = 0; //右括号计数器 for (int i = 0; i case '(': case '[': case '{': { Count_L++;//左括号计数器计数 Push(S, str[i]); //读取到左括号则入栈等待 } break; case ')': { Count_R++;//右括号计数器计数 if (!StackEmpty(S) && GetTop(S) == '(') //读取到右括号则出栈匹配 { Pop(S);//匹配成功则将当前栈内左括号出栈 } } break; case ']': { Count_R++;//右括号计数器计数 if (!StackEmpty(S) && GetTop(S) == '[') { Pop(S); } } break; case '}': { Count_R++;//右括号计数器计数 if (!StackEmpty(S) && GetTop(S) == '{') { Pop(S); } } break; } } if (StackEmpty(S) && Count_L == Count_R) //栈为空栈且左括号数=右括号数即没有出现不匹配情况，则匹配成功 return OK; else if (!StackEmpty(S) && Count_L > Count_R) //栈不为空栈且左括号数>右括号数，则左括号多余 return E_L; else if (StackEmpty(S) && Count_L |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |