#ifndef __MATCHBRACKETS_H__
#define __MATCHBRACKETS_H__
#include<stdio.h>
#include<assert.h>
#include<string.h>
#define MaxSize 20
typedef char SDataType;
typedef struct Stack
{
int top;
SDataType _arry[MaxSize];
} Stack;
void MatchBrackets(Stack* ps, int sz);
int IsBrackets(char arry[], int i);
int StackSize(Stack* ps);
void StackPush(Stack* ps, SDataType data, char arry[]);
void StackPop(Stack* ps);
int StackEmpty(Stack* ps);
void StackInit(Stack* ps);
#endif //__MATCHBRACKETS_H__
//#include"MatchBrackets.h"
int IsBrackets(char arry[], int i)
{
if (('(' == arry[i]) || (')' == arry[i]) || ('[' == arry[i]) || (']' == arry[i]) || ('{' == arry[i]) || ('}' == arry[i]))
return 1;//是括号
else
return 0;
}
int StackSize(Stack* ps)
{
assert(ps != NULL);
return ps->top;
}
void StackPush(Stack* ps, SDataType data)
{
assert(ps != NULL);
if (ps->top == MaxSize)
return;
else
{
ps->_arry[ps->top] = data;
ps->top++;
}
}
void StackPop(Stack* ps)
{
assert(ps != NULL);
if (ps->top)
ps->top--;
}
int StackEmpty(Stack* ps)
{
assert(ps != NULL);
if (0 == ps->top)
return 1;
else
return 0;
}
void StackInit(Stack* ps)
{
assert(ps != NULL);
ps->top = 0;
}
void MatchBrackets(Stack* ps, int sz, char arry[])
{
int i = 0;
int k = 0;//因为传的是指针,所以要定义一个形参
assert(ps != NULL);
//char ch = 0;
while (i < sz)
{
if (IsBrackets(arry, i))//是括号
{
//如果是左括号,入栈
if (('(' == arry[i]) || ('[' == arry[i]) || ('{' == arry[i]))
{
StackPush(ps, arry[i]);
i++;
continue;
}
else if ((')' == arry[i]) || (']' == arry[i]) || ('}' == arry[i]))
{
if (0 == ps->top) //判断栈是否为空,若为空,则右括号比左括号多
{
printf("右括号比左括号多!\n");
return;
}
else
{
k = ps->top;
char ch = ps->_arry[--k];//error:ch = ps->_arry[--(ps->top)]---因为ps->top已经减1了,传递是指针,所以实参ps->top也-1了(此时ps->top已经指向栈顶了),但在下边要出栈(先-1,再出栈,出的就不是栈顶指针了,就会出错,所以我们要定义一个形参k,对形参的改变不会引起对实参的改变),
//如果右括号与左括号匹配,左括号出栈
if (((')' == arry[i]) && ('(' == ch)) ||
((']' == arry[i]) && ('[' == ch)) ||
(('}' == arry[i]) && ('{' == ch)))
{
StackPop(ps);
i++;
continue;
}
else
{
printf("括号匹配出错!\n");
return;
}
}
}
}
else //不是括号,不用操作,直接向后走
{
i++;
}
}
if (!StackEmpty(ps))
{
printf("左括号比右括号多!\n");
}
else
{
printf("匹配正确!\n");
}
}
//#include"MatchBrackets.h"
int main()
{
Stack s;
int sz = 0;
char ch[250];
int n=250;
while(n--)
{
StackInit(&s);
scanf("%s",ch);
getchar();
sz = strlen(ch);
MatchBrackets(&s, sz, ch);
}
return 0;
}
//参考:https://blog.csdn.net/huaijiu123/article/details/81806636
写个while循环
条件是栈不为空并且字符串遍历未结束
两层循环,
外层是压入数据,
内层是弹出数据,
符合条件时,进入内层循环,匹配成功后,跳出内层,进入外层,继续压入数据