括号匹配问题详解

括号匹配问题详解括号匹配问题,经典题目详解,包你一看就会!!_括号匹配问题

直接看题!!

括号匹配问题详解

typedef char STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;   //栈顶的位置
	int capacity; //容量
}ST;

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;

}


void StackDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//容量不足,需要进行扩容
	if (ps->top == ps->capacity)
	{
		//增大容量
		int NewCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		//对a指向的数组空间进行增容
		ps->a = (STDataType*)realloc(ps->a, NewCapacity * sizeof(STDataType));
		//检查
		if (ps->a == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->capacity = NewCapacity;

	}
	//增容之后再入栈
	//top是从0位置开始所以是先使用再++
	ps->a[ps->top] = x;
	ps->top++;
}


void StackPop(ST* ps)
{
	assert(ps);

	assert(ps->top > 0);

	--ps->top;

}

bool StackEmpty(ST* ps)
{
	assert(ps);

	if (ps->top > 0)
	{
		return false;
	}
	else
	{
		return true;
	}

	//return ps->top == 0;
}

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

	//top是从0开始的
	return ps->a[ps->top - 1];

}

  这道题不能用直接数括号数量来进行解答,因为还涉及顺序的问题。括号的匹配用什么来做是最合适的呢?答案是用栈。

  根据栈独有的特点,具体操作:1、属于左括号,进行入栈处理。2、属于右括号进行出栈处理,然后进行匹配,不匹配就报错。我们既然选择用C语言来实现,就需要我们自己提前实现一个栈结构。代码如下:

在栈的基础上再进行括号匹配的实现,代码如下:


bool isValid(char * s)
{
    ST st;

    //初始化栈
    StackInit(&st);

    while(*s)
    {
        //如果是左括号就入栈
        if(*s == '(' || *s == '[' || *s == '{')
        {
            //入栈
            StackPush(&st, *s);
            ++s;
        }
     
        else
        {
            //若到了这里*s一定是右括号

            //若只有右括号,栈为空
            if(StackEmpty(&st))
            {
                return false;
            }

            //取出栈顶元素
            char top = StackTop(&st);

            //出栈
            StackPop(&st);
            
            //这里不要判断相等,判断相等是不能立即得出结果的,括号有三个种类,
            //就算第一种匹配了,还要判断第二种或者第三种是否匹配
            //所以这里应判断不等,一旦这种括号不相等就立即能得到结果
            if((*s == ')' && top != '(')
            || (*s == ']' && top != '[')
            || (*s == '}' && top != '{'))
            {

                StackDestroy(&st);

                //但凡有不匹配都会return false
                return false;
            }
            else
            {
                //到这里说明匹配上了,继续比
                ++s;
            }

        }
    }

    //栈为空,说明所有左括号都匹配了,反之,不为空,返回false
    bool tmp = StackEmpty(&st);
    
    StackDestroy(&st);

    //到这里就说明全部都匹配上了
    return tmp;
}

​​​​​​​

到目前为止我们所实现出来的代码,逻辑上貌似没有什么问题,但是当我们进行测试的时候,出现了有测试用例没有通过。说明我们的程序还是存在问题的。这就需要我们根据测试用例来对程序进行分析了,一般的方法是根据显示出的不通过的测试用例带入到程序中,然后自己根据程序的逻辑走一遍,相当于执行一遍程序,这样很大可能会发现程序的问题所在。

括号匹配问题详解

根据上图的信息我们得知输入的是“[”,也就是*s为‘[’,进入while语句,紧接着进入if语句,然后进行入栈,++s,此时的*s为 ‘\0’,跳出while循环,最后执行return true;所以才会输出true。但是只有一个括号是不可能匹配的,应该输出false才对。知道了病因,我们就可以对症下药了。具体怎么解决呢?既然他只有一个左括号,但是会跳出while语句,因此我们可以再while语句下面做文章。如果括号都匹配上了,那栈里面应该是没有元素的,所以我们可以在while语句执行完成之后再对进行判空,栈为空就说明都匹配上了,如果栈里面还有落单得到括号。那就肯定没有匹配上。

​​​​​​​括号匹配问题详解

括号匹配问题详解

当我们修改之后,再进行测试,发现还是有执行错误,根据测试用例可以看到,他这次给的是“]”,我们还是按照上面说的方法进行操作。会发现它给的错误信息显示StackTop这个函数的ps->top > 0 是有问题的,再看看一下此函的具体实现,显而易见,是assert语句给出的错误提示,若没有assert的话这里就是越界错误,你不知道在哪里发生的越界,更不容易让人发现。这里也体现出使用assert好处可见一斑。

括号匹配问题详解

再分析:输入的是右括号,走的是while循环里的else语句,它里面会去取栈顶的元素,但是目前栈里面是没有元素的,不符合assert的判定条件,因此会报断言错误。

括号匹配问题详解

括号匹配问题详解

最后这里还有小细节,在return 之前,我们最好将栈进行销毁,不然就会有内存泄露,但是一般内存泄露是检查不出来的。但是咱们得养成良好的习惯!

今天的文章括号匹配问题详解分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/62236.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注