有效的括号 力扣 栈应用

上班摸鱼打代码@o@

题目描述

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()" 输出：true 示例 2：

输入：s = "()[]{}" 输出：true 示例 3：

输入：s = "(]" 输出：false 示例 4：

输入：s = "([)]" 输出：false 示例 5：

输入：s = "{[]}" 输出：true

提示：

1 <= s.length <= 104 s 仅由括号 '()[]{}' 组成

AC代码

class Solution {
public:
    bool isValid(string s) {
    	stack<char>temp;
    	for(auto & it:s)if(it=='('||it=='['||it=='{')temp.push(it);
    	else if(temp.empty()||it==')'&&temp.top()!='('||it==']'&&temp.top()!='['||it=='}'&&temp.top()!='{')return false;
    	else temp.pop();
    	return temp.empty();
    }
};

思路分析

成双成对……

首先得看懂题目，到底哪些是满足要求的字符串，我举一些例子：

最明显的：() [] {}

嵌套的：{[()]}

但是这样也可以：{ () ([]) [] {} }

这种部分式对称，我们可以用栈来解决。

我们按照处理一对弹出一对的方式，遍历字符串，遇到（ 就压栈，遇到 ），如果式满足要求的那么它前一个一定是 （ ，因为我们用栈是处理一对弹出一对，不会出现嵌套的一对，但是栈中可以出现{ [ ( 这样的。遍历完毕之后判断栈是不是空的，如果是空的，说明都是一对一对的，因为只有是一对才会弹栈，如果最后栈不是空的，说明有一只单身狗，或者是很多只单身狗。

代码中可以看到else if的条件判断中也判断了栈是否为空，因为有一种情况是第一个字符串就是右括号，那么就不会压栈，如果在栈为空的情况下弹栈会出错，而且第一个字符就是右括号的话，那就直接把它给寄了return回去。