1.问题

假设表达式中允许包含两种括号[ ]和( ),我们检验在表达式中是否是正确的格式，比如3+[3*(2-1)+1]是正确的格式，但是要是3+[(2+1])+1就不是正确的格式，那么我们如何进行检验呢

2.算法实现步骤

初始化一个空栈S

设置一个标记性变量flag,用来标记匹配结果以控制循环及返回结果,1表示正确的匹配.表示错误的匹配,flag的初始值为1

扫描表达式依次读入字符ch，如果表达式扫描完毕且flag非0，则循环执行以下操作

• 若ch为‘[’或者‘(’则将其压入栈中
• 若ch是‘)’则根据当前栈顶元素得到值分情况考虑，若栈顶元素是‘(’那么正确匹配，否则错误匹配，将flag置为0
• 若ch是‘]’则根据当前栈顶元素得到值分情况考虑，若栈顶元素是‘[’那么正确匹配，否则错误匹配，将flag置为0

退出循环后，如果栈空且flag为1,那么匹配正确，否则匹配错误

3.代码详解

#include<iostream> using namespace std; #define MAXSIZE 100 #define SElemType int #define Status int #define OK 1 #define ERROR 0 typedef struct{SElemType *base;SElemType *top;int stacksize; }SqStack; Status InitStack(SqStack &S)//初始化栈 {S.base=new SElemType[MAXSIZE];if(!S.base)exit(0);S.top=S.base;S.stacksize=MAXSIZE;return OK; } Status Push(SqStack &S,SElemType e)//栈顶加入一个元素 {if(S.top-S.base==S.stacksize)return ERROR;*S.top++=e;return OK; } Status Pop(SqStack &S,SElemType &e)//栈顶弹出一个元素 {if(S.base==S.top)return ERROR;e=*--S.top;return OK; } Status Empty(SqStack S)//判断栈是否为空 {if(S.base==S.top)return OK;return ERROR;} SElemType GetTop(SqStack &S)//得到栈顶元素 {if(S.top!=S.base)return *(S.top-1);} Status Matching(SqStack &S)//括号的匹配 {InitStack(S);int flag=1;char ch;cin>>ch;//我们一个字符一个字符的输入表达式SElemType x;while(ch!='#'&&flag){switch(ch){case '[':case '(':Push(S,ch);break;case ')':if(!Empty(S)&&GetTop(S)=='(')Pop(S,x);else flag=0;break;case ']':if(!Empty(S)&&GetTop(S)=='[')Pop(S,x);else flag=0;break;}cin>>ch; }if(Empty(S)&&flag)return OK;elsereturn ERROR;} int main() {SqStack S;int a=Matching(S);if(a==0)cout<<"匹配失败";elsecout<<"匹配成功"; }

例子1：3+[3*(2-1)+1]

例子2：3+[(2+1])+1

总结

以上是生活随笔为你收集整理的用栈实现括号匹配的检验的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。