[算法] leetcode_括号匹配问题

朴灿烈づ我的快乐病毒、 2023-01-22 13:57 18阅读 0赞

# 1.前言 #

此篇文章中，不会对栈的基本操作进行赘述，如果需要查看栈的具体操作，可以点击这个链接: [栈的基本操作以及利用栈实现二进制计算器][Link 1]

# 2.题目详情 #

20. 有效的括号
    	给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
    	有效字符串需满足：
    	左括号必须用相同类型的右括号闭合。
    	左括号必须以正确的顺序闭合。
     
    	示例 1：
    	输入：s = "()"
    	输出：true
    
    	示例 2：
    	输入：s = "()[]{}"
    	输出：true
    
    	示例 3：
    	输入：s = "(]"
    	输出：false
    
    	示例 4：
    	输入：s = "([)]"
    	输出：false
    
    	示例 5：
    	输入：s = "{[]}"
    	输出：true
     
    
    	提示：
    	1 <= s.length <= 104
    	s 仅由括号 '()[]{}' 组成
    
    	https://leetcode-cn.com/problems/valid-parentheses/

# 3.思路分析 #

题目要求对输入的括号进行匹配，如果全部匹配完成，则返回true，如果没有匹配项，则返回false。  
  可以观察输入字符串的结构，如果正常每个括号都有匹配项的话，那利用栈结构，遇到左括号入栈对应的右括号，遇到右括号判断栈顶元素是否相同，相同则出栈。最后判断栈内是否还有剩余元素，有则一定不匹配。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]

# 4. 代码 #

// 判断当前字符是否为左括号，如果是则进行入栈。如果是右括号，则代表栈顶一定有与之匹配的左括号，如果没有匹配项则当前括号不匹配
    bool isValid(char* s) 
    { 
    	if (strlen(s) <= 1)
    		return false;
    
    	Stack ps;
    	StackInit(&ps);
    
    	bool flag = true;
    
    	for (int i = 0; i < strlen(s); i++)
    	{ 
    		// 如果当前字符是左括号，则入栈对应的右括号
    		if ('(' == s[i])
    		{ 
    			StackPush(&ps, ')');
    		}
    		else if ('[' == s[i])
    		{ 
    			StackPush(&ps, ']');
    		}
    		else if ('{' == s[i])
    		{ 
    			StackPush(&ps, '}');
    		}
    		else
    		{ 
    			// 如果当前元素为右括号，则判断栈顶元素是否相同，如果相同则出栈栈顶元素
    			if (!StackEmpty(&ps) && StackTop(&ps) == s[i])
    			{ 
    				StackPop(&ps);
    			}
    			else
    			{ 
    				flag = false;
    				break;
    			}
    		}
    	}
    
    	// 最后判断栈是否为空，如果不为空则说明最后入栈的括号为左括号，并且没有右括号继续入栈
    	if (!StackEmpty(&ps))
    		flag = false;
    
    	StackDestroy(&ps);
    	return flag;
    }

[Link 1]: https://blog.csdn.net/weixin_43717520/article/details/115415308?spm=1001.2014.3001.5501
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221020/d9be8198a82743c589530d61c3673efb.png