括号配对

迈不过友情╰ 2022-08-25 05:28 209阅读 0赞

\#define TRUE 1  
\#define FALSE 0  
\#define STACK\_INIT\_SIZE 10002

\#include "iostream"  
\#include "cstdlib"  
\#include "cstdio"  
\#include "cstring"

using namespace std;

typedef int Status; //Status 相当于 int

typedef struct Stack  
\{  
char \* base;  
char \* top;  
\}SqStack;

//\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*函数的声明\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

void  InitStack(SqStack &S) //创建一个空栈  
\{

S.base = (char \*)malloc(sizeof(char) \* STACK\_INIT\_SIZE);  
S.top = S.base;  
\}

Status StackEmpty(SqStack S)//判断是否为空  
\{  
if(S.top == S.base) return TRUE;  
else return FALSE;  
\}

void Push(SqStack &S,char e )//插入元素e为新的栈顶元素  
\{  
\* S.top++ = e;  
\}  
void Pop(SqStack &S)//出栈  
\{  
S.top--;  
\}

char GetTop(SqStack S)  
\{  
return \*(S.top-1);  
\}

void Matching()  
\{  
SqStack S;//定义一个栈  
InitStack(S);  
int flag = 1;  
char str\[10002\];  
cout<<"\*\*\*\*\*\*\*\*\*\*\*\*请出如括号串（只包含“ (,),\{,\},\[,\] ”）\*\*\*\*\*\*\*\*\*\*\*"<<endl;  
cin>>str;  
for(int i=0;i<strlen(str); ++i)\{//  (\[\[\]()\])  
if(StackEmpty(S) && (str\[i\] == '\]' || str\[i\] == ')'|| str\[i\] == '\}'))\{//第一个字符就为‘\]’或‘)’，直接输出No  
flag = 0; break;  
\}  
if(str\[i\] == '(' || str\[i\] == '\['|| str\[i\] == '\{' ) Push(S,str\[i\]);//接受到‘（’或‘\[’后入栈

if( str\[i\] == '\]' )\{ //接受的为‘\]’  
if(GetTop(S)== '\[') Pop(S);//如果栈顶为'\['，则出栈，否则括号不匹配，退出循环  
else \{ flag = 0; break;\}  
\}  
if( str\[i\] == ')' )\{ //接受的为‘)’  
if( GetTop(S)== '(' ) Pop(S); //如果栈顶为')'，则出栈，否则括号不匹配，退出循环  
else  \{ flag = 0; break;\}  
\}  
if( str\[i\] == '\}' )\{ //接受的为‘\}’  
if( GetTop(S)== '\{' ) Pop(S); //如果栈顶为'\}'，则出栈，否则括号不匹配，退出循环  
else \{ flag = 0; break;\}  
\}  
\}  
if(flag && StackEmpty(S)) cout<<"Yes,括号匹配！"<<endl;  
if(!flag || !StackEmpty(S) )cout<<"No，括号不匹配！"<<endl;  
free(S.base );  
\}  
//\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*主函数\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*  
int main()  
\{  
int door = 1;  
do\{  
Matching();  
cout<<"是否要继续检测下一组括号(Y/N)：";  
char ch;  
cin>>ch;  
if(ch == 'N'|| ch == 'n') door = 0;  
\}while(door);  
  
return 0;  
\}