栈在括号匹配中的应用
思路:
1.遍历字符数组
2.if为左括号,则入栈;
if为右括号,
1)空栈---返回false
2)出栈e,if不匹配返回false,if匹配则继续循环
3.循环结束,判断栈是否为空.if为空栈,返回true,if非空,返回false
主要代码
1.判断左括号则入栈
if (str[i]=='['|| str[i] == '(' || str[i] == '{')
push(s, str[i]);
2.如果右括号先判断是否为空栈
if (stackEmpty(s))
return false;
3.判断右括号,出栈,判断是否为完整的括号
char e;
pop(s, e);
if (e =='{'&& str[i]!='}')
{return false;}
if (e == '(' && str[i] != ')')
{ return false; }
if (e == '[' && str[i] != ']')
{ return false; }
4.attention:计算字符数组长度
int length = (sizeof(str) / sizeof(str[0]))-1;
因为字符数组会默认在尾部加入'/0',所以计算得到的长度会比实际长度多1位.
5.代码
bool bracketCheck(char str[] ,int length) {
//定义+初始化栈
sqStack s;
init(s);
for (int i = 0; i < length; i++)
{//判断为左括号还是右括号
//左括号--入栈
if (str[i]=='['|| str[i] == '(' || str[i] == '{')
{
push(s, str[i]);
}
else {
//右括号--出栈
//1.判断是否空栈--空false
if (stackEmpty(s))
{
return false;
}
char e;
//判断左括号右括号是否相符
pop(s, e);
if (e =='{'&& str[i]!='}')
{
return false;
}
if (e == '(' && str[i] != ')')
{
return false;
}
if (e == '[' && str[i] != ']')
{
return false;
}
}
}
return stackEmpty(s);
}
完整代码
#include<stdio.h>
#define MaxSize 10
//顺序栈定义
typedef struct sqStack {
char data[MaxSize];
int top;
}sqStack;
//初始化
void init(sqStack& s) {
s.top = -1;
}
//进栈
bool push(sqStack &s,char e) {//e输入数据
//判断是否栈满
if (s.top==MaxSize-1)
{
return false;
}
s.data[++s.top] = e;
return true;
}
//出栈
bool pop(sqStack& s, char &e) {
//判断是否空栈
if (s.top==-1)
{
return false;
}
e=s.data[s.top--];
return true;
}
//判断空栈
bool stackEmpty(sqStack s) {
if (s.top == -1)
{
return true;
}
return false;
}
//读取栈顶元素
bool getTop(sqStack &s,char &e) {
//判断是否空栈
if (s.top == -1)
{
return false;
}
e = s.data[s.top];
return true;
}
bool bracketCheck(char str[] ,int length) {
//定义+初始化栈
sqStack s;
init(s);
for (int i = 0; i < length; i++)
{//判断为左括号还是右括号
//左括号--入栈
if (str[i]=='['|| str[i] == '(' || str[i] == '{')
{
push(s, str[i]);
}
else {
//右括号--出栈
//1.判断是否空栈--空false
if (stackEmpty(s))
{
return false;
}
char e;
//判断左括号右括号是否相符
pop(s, e);
if (e =='{'&& str[i]!='}')
{
return false;
}
if (e == '(' && str[i] != ')')
{
return false;
}
if (e == '[' && str[i] != ']')
{
return false;
}
}
}
return stackEmpty(s);
}
int main() {
char str[] = "{{[]([])}}";
int length = (sizeof(str) / sizeof(str[0]))-1;//因为这里的长度还加入了'/0',所以会比书写的多一位
if (bracketCheck(str, length)) {
printf("配对成功!");
}
else {
printf("sorry,配对失败!");
}
}