C语言题目练习5——有效的括号

有效的括号

思路

将字符串遍历，如果是当前字符是左括号就入栈，如果当前字符是右括号就将它与取到的栈顶元素进行匹配，如果不匹配就return false，然后再出栈（删除当前元素），在出栈前需要判断栈是否为空，如果为空说明栈目前没有左括号，显然这是不匹配的（左括号应该在左边，右括号在右边）return false，遍历字符串结束，这里需要判断栈是否为空，避免有左括号没有匹配的情况，为空返回true，不为空返回false。

注意

可能有一些难理解，我们一步步来看~

首先将栈的一些基本实现拿过来用

//栈的基本实现
typedef char StackDatatype;
//这个题目中栈保存的数据是字符
typedef struct Stack
{
	StackDatatype* arr;
	int top;
	int capacity;
}Stack;
//初始化
void StackInit(Stack* ps)
{
	assert(ps);

	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}
//入栈
void StackPush(Stack* ps, StackDatatype x)
{
	assert(ps);
	//判断容量是否足够
	if (ps->top == ps->capacity)//空间已满
	{
		int newcapacity = (ps->capacity == 0) ? 4 : 2 * (ps->capacity);
		StackDatatype* temp = realloc(ps->arr, sizeof(StackDatatype) * newcapacity);
		if (temp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		else
		{
			ps->arr = temp;
			ps->capacity = newcapacity;
		}
	}
	//空间足够
	ps->arr[ps->top++] = x;
}

//判断栈是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
	//栈没有元素
}
//取栈顶元素
StackDatatype StackTop(Stack* ps)
{
	assert(ps);
	//栈不能为空
	assert(!StackEmpty(ps));

	return ps->arr[ps->top - 1];
}


//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

//获取栈有效个数
int StackCount(Stack* ps)
{
	assert(ps);
	return ps->top;
}

//栈销毁
void StackDestory(Stack* ps)
{
	assert(ps);
	if (ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

实现函数代码及详细解释：

bool isValid(char* s)
{
    assert(s);//字符串地址有效
    Stack st;
    StackInit(&st);//初始化栈
    char* pcur = s;
    //遍历字符串左括号入栈
    while ((*pcur) != '\0')
    {
        if ((*pcur) == '(' || (*pcur) == '[' || (*pcur) == '{')
        {
            //入栈
            StackPush(&st, (*pcur));
        }
        //！！！每一次返回true或者false前要进行栈销毁
        else//遇到右括号取栈顶元素比较是否匹配
        {
            if (StackEmpty(&st))
                //栈为空,目前只有右括号，前面没有左括号匹配
            {
                StackDestory(&st);
                return false;
            }
            //取栈顶元素比较
            StackDatatype re = StackTop(&st);
            //当前字符与栈顶元素不匹配
            if ((re == '(' && *pcur != ')') ||
                (re == '[' && *pcur != ']') ||
                (re == '{' && *pcur != '}'))
            {
                StackDestory(&st);
                return false;
            }
            //满足当前数据出栈
            StackPop(&st);
        }
        pcur++;//继续往后面遍历
    }
    //判断栈是否为空
    //栈不为空，还有左边括号没有匹配
    /*if(StackEmpty(&st))
    {
        StackDestory(&st);
        return true;
    }
    else
    {
        StackDestory(&st);
        return false;
    }*/
    //优化
    bool ret = StackEmpty(&st) ? true : false;
    //使用bool类型保存返回值
    StackDestory(&st);
    return ret;
}

结合着代码来看，是不是更加清晰呢？我们也就完成了这一段代码，提交一下看能否通过？

提交通过~感觉知识又以一种奇怪的方式进入了脑子~

今日练习结束，期待与各位未来的优秀程序员交流，有什么问题请私信~~~