LeetCode 20.有效括号 详解(c语言实现) (????)?

发布时间:2024年01月05日

题目详情:

?思路:Step1:如果是左括号,入栈

? ? ? ? ? Step2:如果是右括号,就出栈顶的元素与右括号进行比对,如果匹配,继续,直到都匹配成功结束。否则退出,直接返回false.

栗子:1.? {[()]}? ? ? 左括号? '{' '[' '('? 入栈后与栈顶的右括号 )')'? ']' '}' 依次进行匹配,结果发现匹配,返回true.

2.? [(]}? ? 左括号 '['? '('? 入栈,遇到右括号 ']' 与栈顶的左括号 '('? ?匹配,匹配不上,返回false.

注意:无论匹配或者不匹配,都要摧毁栈,防止内泄漏

用c语言实现栈,没法直接引用,这里需要自己创建一个栈,在完成上述操作。如果还不会栈的小伙伴可以看看我的这篇博客?【数据结构】栈【详解】?? ? ? ? ??-CSDN博客

?

?栈的实现:

typedef int STDataType;
typedef struct Stack//栈的声明与定义
{
	STDataType* a;//定义一个指针,用于后续存储空间
	int top;
	int capacity;
}ST;
//初始化栈
void StackInit(ST* ps)
{
	assert(ps);//为初始化的栈开辟一个空间
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
//同时让其容量为当前栈开辟的空间
	ps->capacity = 4;
	ps->top = 0;
}
//摧毁栈
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

// 入栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	// 满了->增容,每次扩充的容量是当前的二倍
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{//开辟玩空间后,让栈的指针指向这片空间,同时栈的容量增加
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}

	ps->a[ps->top] = x;
	ps->top++;
}

// 出栈
void StackPop(ST* ps)
{
	assert(ps);
	// 栈空了,调用Pop,直接中止程序报错
	assert(ps->top > 0);
    //出栈直接让栈顶减一
	//ps->a[ps->top - 1] = 0;
	ps->top--;
}
//返回栈顶的元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	// 栈空了,调用Top,直接中止程序报错
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}
//返回栈的大小
int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

?

?括号匹配函数的实现:

//测试运行函数
bool isValid(char* s) 
{
    ST st;
    StackInit(&st);
    while(*s!='\0')
    {   //通过指针来遍历数组,直到终止
//这里判断字符,左括号进栈,右括号出栈
         switch(*s)
         {
             case '{':
             case '[':
             case '(':
             {
                 StackPush(&st,*s);
                 ++s;
                 break;//每次进栈就进行下一次循环,同时++s
             }
             case '}':
             case ']':
             case ')':
             {//如果没有左括号,就说明只有右括号,栈内为空,就直接返回false
             //记得要摧毁栈,防止内存泄漏
                 if(StackEmpty(&st))
                 {
                     StackDestory(&st);
                     return false;
                 }
                 //若栈不为空,就   取栈顶元素进行比对
                 //若为预期对应的右括号,匹配成功,同时++s,移向下一个位置继续匹配
                 char top=StackTop(&st);
                 StackPop(&st);
                 //不匹配就返回flase
                 if((*s=='}' && top!='{')
                 || (*s==']' && top!='[')
                  || (*s==')' && top!='('))
                  {
                      StackDestory(&st);
                      return false;
                  }
                  else
                  {
                    ++s;
                  }
             }
             default:
             break;
         }
    }
    //若当前栈为空,说明已经匹配完成,都匹配,返回true
    bool ret=StackEmpty(&st);
    StackDestory(&st);
    return ret;
}

如代码所示:通过遍历*s,来进行括号的匹配。如果字符是左括号就入栈StackPush,并使*s++。如果只有右括号而没有左括号,说明栈为空,这时直接摧毁栈并返回false。接着依次取栈顶元素与当前右括号匹配,成功就继续,直到最后一个匹配完成(这时判断条件是完成上述操作后StackEmpty是真),返回true,否者返回false。

?

最后完整代码:?

typedef int STDataType;
typedef struct Stack//栈的声明与定义
{
	STDataType* a;//定义一个指针,用于后续存储空间
	int top;
	int capacity;
}ST;
//初始化栈
void StackInit(ST* ps)
{
	assert(ps);//为初始化的栈开辟一个空间
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
//同时让其容量为当前栈开辟的空间
	ps->capacity = 4;
	ps->top = 0;
}
//摧毁栈
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

// 入栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	// 满了->增容,每次扩充的容量是当前的二倍
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{//开辟玩空间后,让栈的指针指向这片空间,同时栈的容量增加
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}

	ps->a[ps->top] = x;
	ps->top++;
}

// 出栈
void StackPop(ST* ps)
{
	assert(ps);
	// 栈空了,调用Pop,直接中止程序报错
	assert(ps->top > 0);
    //出栈直接让栈顶减一
	//ps->a[ps->top - 1] = 0;
	ps->top--;
}
//返回栈顶的元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	// 栈空了,调用Top,直接中止程序报错
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}
//返回栈的大小
int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}
//若为空,返回空栈
bool StackEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}
//测试运行函数
bool isValid(char* s) 
{
    ST st;
    StackInit(&st);
    while(*s!='\0')
    {   //通过指针来遍历数组,直到终止
//这里判断字符,左括号进栈,右括号出栈
         switch(*s)
         {
             case '{':
             case '[':
             case '(':
             {
                 StackPush(&st,*s);
                 ++s;
                 break;//每次进栈就进行下一次循环,同时++s
             }
             case '}':
             case ']':
             case ')':
             {//如果没有左括号,就说明只有右括号,栈内为空,就直接返回false
             //记得要摧毁栈,防止内存泄漏
                 if(StackEmpty(&st))
                 {
                     StackDestory(&st);
                     return false;
                 }
                 //若栈不为空,就   取栈顶元素进行比对
                 //若为预期对应的右括号,匹配成功,同时++s,移向下一个位置继续匹配
                 char top=StackTop(&st);
                 StackPop(&st);
                 //不匹配就返回flase
                 if((*s=='}' && top!='{')
                 || (*s==']' && top!='[')
                  || (*s==')' && top!='('))
                  {
                      StackDestory(&st);
                      return false;
                  }
                  else
                  {
                    ++s;
                  }
             }
             default:
             break;
         }
    }
    //若当前栈为空,说明已经匹配完成,都匹配,返回true
    bool ret=StackEmpty(&st);
    StackDestory(&st);
    return ret;
}

博客到这里也是结束了,喜欢的小伙伴可以点赞加关注支持下博主,这对我真的很重要~~

?

文章来源:https://blog.csdn.net/2302_79862386/article/details/135409209
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。