用C语言实现“括号匹配“问题

初阶牛

发布于 2023-10-14 17:46:58

6740

文章被收录于专栏：C语言基础C语言基础

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨ 🐻推荐专栏1: 🍔🍟🌯C语言初阶 🐻推荐专栏2: 🍔🍟🌯C语言进阶 🔑个人信条: 🌵知行合一 🍉本篇简介:>:记录力扣 “括号匹配问题”

题目介绍:

声明:题目来源于力扣. 题目链接:传送门

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。

示例

示例1:

输入：s = “()” 输出：true

示例2:

输入：s = “()[]{}” 输出：true

示例3:

输入：s = “(]” 输出：false

解题思路:

此题我们使用’栈’这个结构. 每个左括号都与右边最近的右括号匹配。所以我们可以用栈来保存每个等待匹配的右括号的左括号是什么，只要匹配成功就把元素弹出，当字符串遍历结束时如果栈为空，就说明所有括号都互相匹配了。那么这个字符串就是有效的。

例如:

情况1:(右括号过多或者未匹配)

字符串没有遍历结束,而遇到右括号时,栈已经为NULL,则直接返回false. 当0 ,1 ,2入栈. 3与2匹配成功,则2出栈. 4与1匹配成功,则1出栈. 5与0匹配成功,0出栈. 此时6为右括号,在栈顶并没有等到他想要的人,因为栈已经为NULL了,则返回false.

情况2:

左字符串依次入栈,右字符串依次出栈,最后字符遍历结束,而栈也是空栈,则表示括号匹配成功. 当0 ,1 ,2 ,3入栈. 4与3匹配成功,则3出栈. 5与2匹配成功,则2出栈. 6与1匹配成功,则1出栈. 7与0匹配成功,则0出栈.

此时栈为NULL,且字符串遍历结束.返回true.

情况3:(左括号过多或者未匹配成功)

左括号过多,即使右括号用完(这个例子没用完),字符串遍历结束,栈中仍有元素(左括号未找到匹配). 栈非空返回false.

步骤: 在C语言中使用栈的结构,需要自己造轮子,先设计一个栈出来,文章结尾已经写出,其次是一定要记得初始化(InitST).

计算字符串的长度
如果字符串是长度为奇数,则直接返回false.
遇见左括号入栈
遇见右括号先判断栈是否为NULL,为空则直接返回false. 不为空,则与栈顶元素比较,如果是匹配成功的则出栈,否则直接返回false
最后如果栈是NULL栈则返回true,否则返回false

代码实现:

bool isValid(char* s) {
  	ST st1;
	InitST(&st1);//这个别忘了
    int sz=strlen(s);
    if (sz % 2 == 1)
	{
		return false;
	}
    for(int i=0;i<sz;i++)
    {
        if(s[i]=='('||s[i]=='['||s[i]=='{')//左括号进栈
        {
            STPush(&st1,s[i]);
        }
        else//右括号
        {
            if(STEmpty(&st1))//如果碰到右括号,且栈是NULl,则返回false
            {
                return false;
            }
            //如果栈顶与右括号匹配,则出栈
           	if (STTop(&st1) == '(' && s[i] == ')' || STTop(&st1) == '[' && s[i] == ']' || STTop(&st1) == '{' && s[i] == '}')//如果栈顶元素与右括号匹配,则出栈
			{
				STPop(&st1);
			}
           else{
               return false;
           }
        }
    }
    return STEmpty(&st1);
}

上面的实现方式还有一个内存泄漏的危险,因为栈空间并没有被释放,应当在每个返回结果之前调用栈销毁函数(STDestory).

栈的实现:

//栈的实现
//oj题里面不需要写头文件
typedef  char stacktype;
typedef struct stack
{
	stacktype* data;
	int top;
	int capacaity;
}ST;
void InitST(ST* ps);
void STPush(ST* ps, stacktype x);//压栈
void STPop(ST* ps);//出栈

bool STEmpty(ST* ps);//判断是否为空栈
stacktype STTop(ST* ps);//返回栈顶元素
void STDestory(ST* ps);//栈的销毁


//初始化栈
void InitST(ST* ps)
{
	assert(ps);
	ps->top = -1;
	ps->capacaity = 4;
	ps->data = (stacktype*)malloc(ps->capacaity * sizeof(stacktype));

}

//压栈
void STPush(ST* ps, stacktype x)
{
	assert(ps);
	if (ps->top + 1 == ps->capacaity)
	{
		ps->capacaity *= 2;
		stacktype* tmp = (stacktype*)realloc(ps->data, ps->capacaity * sizeof(stacktype));
		if (tmp == NULL)
		{
			printf("增容失败\n");
		}
		ps->data = tmp;
	}
	ps->top++;
	ps->data[ps->top] = x;

}

//出栈
void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	ps->top--;
}

//判断是否为空栈,是空返回真
bool STEmpty(ST* ps)
{
	assert(ps);
	if (ps->top == -1)//如果"栈"为空,则栈顶的下标为-1;
	{
		return true;
	}
	return false;
}

//返回栈顶元素
stacktype STTop(ST* ps)
{
	assert(ps);
	return ps->data[ps->top];//反追栈顶元素
}

//栈的销毁
void STDestory(ST* ps)
{
	assert(ps);
	free(ps->data);//释放栈空间
	ps->data = NULL;
	ps->top = -1;
	ps->capacaity = 0;
}

提交记录: