用栈实现括号匹配
实现思路
- 1.创立一个判断括号是否匹配的函数BracketsCheck
- 2.传参(栈,输入的字符串)
- 3.对字符串中的(、[、{、这三种括号进行匹配
- 4.顺序从左往右进行,依次将符合条件的括号放入栈中,满足FILO原则
- 5.但拿到右括号时进行匹配,如果匹配成功,那么就出栈,如果失败就返回false
栈的基本功能实现
- 定义一个顺序栈
typedef struct {
char data[MAXSIZE];
int top;
}Sqstack;
- 定义一个初始化函数
void InitSqstack(Sqstack& s)
{
s.top = -1;
}
- 定义一个判断栈是否为空的函数
bool StackEmpty(Sqstack& s)
{
if (s.top == -1)
return true;
else
return false;
}
- 定义一个入栈的函数
bool PushSqstack(Sqstack& s,char x)
{
if (s.top == MAXSIZE - 1)
return false;
s.data[++s.top] = x;
return true;
}
- 定义一个出栈的函数
bool PopSqstack(Sqstack& s,char& x)
{
if (s.top == -1)
return false;
x = s.data[s.top--];
return true;
}
判断括号是否匹配的函数(重点)
定义成bool类型的函数,通过返回值来判断是否匹配,其中运用for循环来对字符串来遍历,对里面的字符一一进行判断,通过栈的后入先出的特点,来进行左右符号的匹配
bool BracketsCheck(Sqstack& s, char str[])
{
for(int i=0;str[i] != '\0'; i++)
{
if (str[i] == '(' || str[i] == '[' || str[i] == '{')
PushSqstack(s, str[i]);
else
{
char element;
PopSqstack(s, element);
if (str[i] == ')' && element != '(')
return false;
if (str[i] == ']' && element != '[')
return false;
if (str[i] == '}' && element != '}')
return false;
}
}
return StackEmpty(s);
}
源代码
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAXSIZE 50
typedef struct {
char data[MAXSIZE];
int top;
}Sqstack;
void InitSqstack(Sqstack& s)
{
s.top = -1;
}
bool StackEmpty(Sqstack& s)
{
if (s.top == -1)
return true;
else
return false;
}
bool PushSqstack(Sqstack& s,char x)
{
if (s.top == MAXSIZE - 1)
return false;
s.data[++s.top] = x;
return true;
}
bool PopSqstack(Sqstack& s,char& x)
{
if (s.top == -1)
return false;
x = s.data[s.top--];
return true;
}
/*
* 1.创立一个判断括号是否匹配的函数BracketsCheck
* 2.传参(栈,输入的字符串)
* 3.对字符串中的(、[、{、这三种括号进行匹配
* 4.顺序从左往右进行,依次将符合条件的括号放入栈中,满足FILO原则
* 5.但拿到右括号时进行匹配,如果匹配成功,那么就出栈,如果失败就返回false
*/
bool BracketsCheck(Sqstack& s, char str[])
{
for(int i=0;str[i] != '\0'; i++)
{
if (str[i] == '(' || str[i] == '[' || str[i] == '{')
PushSqstack(s, str[i]);
else
{
char element;
PopSqstack(s, element);
if (str[i] == ')' && element != '(')
return false;
if (str[i] == ']' && element != '[')
return false;
if (str[i] == '}' && element != '}')
return false;
}
}
return StackEmpty(s);
}
int main()
{
Sqstack s;
InitSqstack(s);
char str[MAXSIZE];
printf("请输入一串带有括号的字符串:");
scanf("%s", str);
bool flag=BracketsCheck(s, str);
printf("%d", flag);
return 0;
}
运行结果展示
文章来源:https://www.uudwc.com/A/XkDke/
总结
如果这篇文章对你有帮助的话,可以给我点个关注,我们一起进步!文章来源地址https://www.uudwc.com/A/XkDke/