数据结构：力扣OJ题（每日一练）

清疚 2023-10-14 19:51 40阅读 0赞

## ![9ca51dfa59ca4473919ea735ffaed8b9.png][]题一：有效的括号 ##

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

有效字符串需满足：

1.  左括号必须用相同类型的右括号闭合。
2.  左括号必须以正确的顺序闭合。
3.  每个右括号都有一个对应的相同类型的左括号。
4.  **示例 2：**
    
        输入：s = "()[]{}"
        输出：true

### 思路一： ###

**第一步：**写出数组栈的**结构体**，然后分别写出**栈的初始化，入栈，出栈，获取栈顶元素，销毁栈，检验栈是否为空**的函数；

**第二步：**创建一个**结构体变量，初始化**，while(\*s)决定是否继续循环，用switch找到对应的**前置符号**将他们入栈，如果是**后置符号**，则先**判断ps中是否为空**，然后再判断是否有对应的前置符合，**没有**：直接结束，**有**：继续循环；

**第三步：**创建相应的bool型变量记录SLEmpty()函数的返回值，销毁创建空间。

**注意：OJ题不会判断代码开辟动态内存空间，所以在OJ题，不销毁开辟的动态内存也正确。**

//约定类型方便更改类型
    typedef char STDataType;
    typedef struct Stack
    {
    	STDataType* a;
    	int top;
    	int capacity;
    }SL;
    //初始化
    void SLInit(SL* ps)
    {
    	assert(ps);
    	ps->a = NULL;
    	ps->capacity = ps->top = 0;
    }
    
    //入栈
    void SLPush(SL* ps, STDataType x)
    {
    	assert(ps);
    	//栈顶=容量说明需要扩容
    	if (ps->capacity == ps->top)
    	{
    		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
    		STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newcapacity);
    		if (tmp == NULL)
    		{
    			perror("realloc fail");
    			exit(-1);
    		}
    		ps->capacity = newcapacity;
    		ps->a = tmp;
    	}
    	ps->a[ps->top] = x;
    	//后缀++方便下一次入栈和打印栈顶
    	ps->top++;
    }
    
    //出栈
    void SLPop(SL* ps)
    {
    	assert(ps);
    	//为空情况“0”
    	assert(ps->top > 0);
    	//
    	--ps->top;
    }
    
    
    //获得栈顶元素
    STDataType SLTTop(SL* ps)
    {
    	assert(ps);
    	//为空情况“0”
    	assert(ps->top > 0);
    	int n = (ps->top) - 1;
    	return ps->a[n];
    }
    
    
    //获取栈中有效元素个数
    int SLSize(SL* ps)
    {
    	assert(ps);
    	return ps->top;
    }
    
    //销毁栈
    void SLDestroy(SL* ps)
    {
    	assert(ps);
    	//开辟数组优势：一次全部释放
    	free(ps->a);
    	ps->a = NULL;
    	ps->capacity = ps->top = 0;
    }
    
    // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
    bool SLEmpty(SL* ps)
    {
    	assert(ps);
    	//为“0”说明为NULL
    	if (ps->top == 0)
    	{
    		return true;
    	}
    	return false;
    }
    
    
    //思路一：使用switch
    bool isValid(char * s)
    {
    	SL ps;
    	char val;
    	//初始化
    	SLInit(&ps);
    	while (*s)
    	{
    		switch (*s)
    		{
    		case '(':
    		case '[':
    		case '{':
    				//入栈
    				SLPush(&ps, *s);
    				break;
    		case ')':
    		case '}':
    		case ']':
    				//判断栈是否为空
    				if (SLEmpty(&ps))
    				{
    					//销毁开辟的动态内存
    					SLDestroy(&ps);
    						return false;
    				}
    				//栈顶值
    				val = SLTTop(&ps);
    				//出栈
    				SLPop(&ps);
    				if (*s == ')' && val != '(' ||
    						*s == ']' && val != '[' ||
    						*s == '}' && val != '{')
    				{
    						SLDestroy(&ps);
    						return false;
    				}
    				break;
    		}
    		s++;
    	}
    	bool ret = SLEmpty(&ps);
    	SLDestroy(&ps);
    	return ret;
    }

### 改进简化： ###

原理同上，要实现的内容也同上，不过**简化了switch()语句造成的多次调用**，以及步骤上的增加，**改用if----else语句后**，代码更加的**简洁清晰**，**不需要考虑每种后置符号的操**作，if一次性全部解决了。**总体上减少了三分之一的代码量**。

//约定类型方便更改类型
    typedef char STDataType;
    typedef struct Stack
    {
    	STDataType* a;
    	int top;
    	int capacity;
    }SL;
    //初始化
    void SLInit(SL* ps)
    {
    	assert(ps);
    	ps->a = NULL;
    	ps->capacity = ps->top = 0;
    }
    
    //入栈
    void SLPush(SL* ps, STDataType x)
    {
    	assert(ps);
    	//栈顶=容量说明需要扩容
    	if (ps->capacity == ps->top)
    	{
    		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
    		STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newcapacity);
    		if (tmp == NULL)
    		{
    			perror("realloc fail");
    			exit(-1);
    		}
    		ps->capacity = newcapacity;
    		ps->a = tmp;
    	}
    	ps->a[ps->top] = x;
    	//后缀++方便下一次入栈和打印栈顶
    	ps->top++;
    }
    
    //出栈
    void SLPop(SL* ps)
    {
    	assert(ps);
    	//为空情况“0”
    	assert(ps->top > 0);
    	//
    	--ps->top;
    }
    
    
    //获得栈顶元素
    STDataType SLTTop(SL* ps)
    {
    	assert(ps);
    	//为空情况“0”
    	assert(ps->top > 0);
    	int n = (ps->top) - 1;
    	return ps->a[n];
    }
    
    
    //销毁栈
    void SLDestroy(SL* ps)
    {
    	assert(ps);
    	//开辟数组优势：一次全部释放
    	free(ps->a);
    	ps->a = NULL;
    	ps->capacity = ps->top = 0;
    }
    
    // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
    bool SLEmpty(SL* ps)
    {
    	assert(ps);
    	//为“0”说明为NULL
    	if (ps->top == 0)
    	{
    		return true;
    	}
    	return false;
    }
    
    
    //改进简化内容if——else
    bool isValid(char * s)
    {
    	SL ps;
    	char val;
    	//初始化
    	SLInit(&ps);
    	while (*s)
    	{
    	     if(*s == '(' || *s == '{' || *s == '[')
    		{
    		    //入栈
    		    SLPush(&ps, *s);
    		}
    		else
    		{
    					//判断栈是否为空
    		    if (SLEmpty(&ps))
    		    {
    			//销毁开辟的动态内存
    			SLDestroy(&ps);
    			return false;
    		    }
    			//栈顶值
    			val = SLTTop(&ps);
    			//出栈
    			SLPop(&ps);
    			if (*s == ')' && val != '(' ||
    				*s == ']' && val != '[' ||
    				*s == '}' && val != '{')
    			{
    				SLDestroy(&ps);
    				return false;
    			}
    		}
    		s++;
    	}
    	bool ret = SLEmpty(&ps);
    	SLDestroy(&ps);
    	return ret;
    }

## 本人实力有限可能对一些地方解释的不够清晰，可以自己尝试读代码，望海涵！ ##

[9ca51dfa59ca4473919ea735ffaed8b9.png]: https://img-blog.csdnimg.cn/9ca51dfa59ca4473919ea735ffaed8b9.png