括号序列Leetcode020（有效的括号）--------＞栈的应用（男女配对）

题目：

力扣

描述：

题解：

java中栈的创建和使用_baobaohui-CSDN博客_java中的栈

思路：

首先在刷完至少两边该题之后我已经知道需要使用栈来解决这题了

但是对于栈的加入和弹出我一直都不知道咋用？

y总的思路我觉得很不错，他把{、]、（ 这些左括号比作女生，女生一般比较被动，所以碰到左括号，都将它放在栈中，而右括号就是男生了，男生比较主动，所以碰到右括号时，会主动去寻找栈顶的女生假如与自己配对，就把这个女生带走，也即弹出栈顶字符。

知道思路后我尝试自己写了一下（正着想）

class Solution {
public:bool isValid(string s) {//先将括号左边的部分全部加入栈中stack<char> stack;for(int i=0;i<s.length();i++){if(s[i]=='('||s[i]=='{'||s[i]=='[') stack.push(s[i]);if(s[i]==')'&&stack.top()=='(') stack.pop();if(s[i]==']'&&stack.top()=='[') stack.pop();if(s[i]=='}'&&stack.top()=='{') stack.pop();}if(stack.empty()) return true;else return false;}
};

正着想的思路一旦碰到先输入右括号的行为就比较头疼了，因为这样的话栈是空的，会报错，比如下面这种：

 那么假如我们反过来，找它不配对的情况呢？就完美解决了这个问题

C++代码

class Solution {
public:bool isValid(string s) {//先将括号左边的部分全部加入栈中stack<char> stack;for(int i=0;i<s.length();i++){if(s[i]=='('||s[i]=='{'||s[i]=='[') stack.push(s[i]);else if(s[i]==')'){if(stack.empty()||stack.top()!='(') return false;else stack.pop();}else if(s[i]==']'){if(stack.empty()||stack.top()!='[') return false;else stack.pop();}else if(s[i]=='}'){if(stack.empty()||stack.top()!='{') return false;else stack.pop();}}if(stack.empty()) return true;else return false;}
};

代码：

Java代码

package Leetcode;import java.util.Stack;public class Leetcode020 {public boolean isValid(String s) {//构造栈用来存储左括号Stack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);//假如是左括号那么入栈if (c == '(' || c == '[' || c == '{') {stack.push(c);}else {if(stack.isEmpty()) return false;char top=stack.pop();if (c == ']' && top!='[') {return false;}if (c == ')' && top!='(') {return false;}if (c == '}' && top!='{') {return false;}}}return stack.isEmpty();}
}