1.1 思路
- 第一种场景是左括号多余了，比如“([{}]()”；第二种场景是括号没多，但是类型不匹配，比如“[{(]}]”；第三种场景是右括号多余了，比如“[{}]())))”。注意：“[{]}”是相当于第二种情况；而“)(”相当于第三种情况，第一个右括号没有左括号匹配，就相当于多了
- 遍历字符串，遇到左括号时，就把对应的右括号入栈，因为这样匹配的时候直接弹出来就直接比较就可以了，方便代码实现
- 遇到右括号时，就判断这个右括号是否就是栈顶的右括号，是则弹出，不是则为false；此时如果右括号多了的情况，比如“[{}]())))”，当遍历到倒数第3个右括号时，此时栈里为空，说明右括号多了，则为false
- 最后如果栈不为空，则说明左括号多了，则为false
1.2 代码
class Solution { public boolean isValid(String s) { Stack<Character> stack=new Stack<>(); char ch; for(int i=0;i<s.length();i++){ ch=s.charAt(i); if(ch=='('){ stack.push(')'); }else if(ch=='{'){ stack.push('}'); }else if(ch=='['){ stack.push(']'); }else if(stack.empty()||stack.peek()!=ch){ return false; }else{ stack.pop(); } } return stack.empty(); } }
2. LeetCode 1047. 删除字符串中的所有相邻重复项
2.1 思路
- 这题类似上述的删除括号的方式，同样是使用栈来删除的
- 先创建栈，然后遍历字符串，栈是用来存遍历过的元素，每遍历一个都要在栈里判断是否遍历过当前的元素/前一个元素是否就是当前的元素，如果是，当前元素就不入栈并且把栈顶元素弹出，这个操作用栈就很方便。只要栈不为空或者栈顶元素与当前元素不相同就可以直接入栈
- 遍历完以后栈里剩下的就是要的字符串的反向，我们可以通过一个新的空的字符串str，然后让str=stack.pop()+str; 就是把栈顶元素放到字符串的后面，这样就可以实现把栈里的元素翻转了，得到的就是我们想要的字符串
2.2 代码
class Solution { public String removeDuplicates(String s) { Stack<Character> stack=new Stack<>(); char ch; for(int i=0;i<s.length();i++){ ch=s.charAt(i); if(stack.empty()||stack.peek()!=ch){ stack.push(ch); }else { stack.pop(); } } String str=""; while(!stack.empty()){ str=stack.pop()+str; } return str; } }
3. LeetCode 150. 逆波兰表达式求值
3.1 思路
- 逆波兰表达式是什么？=> 逆波兰表达式也称后缀表达式，这是方便计算机运算的 =>（1+2）*（3+4）这种就是正常习惯看的中缀表达式 =>而后缀表达式就是类似二叉树的后序遍历，在这里式子就变成了 1 2 + 3 4 + *。这样的题目就比较适合用栈来做
- 如何做题？遍历字符串数组，题目里是每个字符作为一个字符串，当遇到数字就入栈；当遇到运算符就出栈两个元素，第一个出栈的数字放在运算符的右边，第二个出栈的数字放在运算符的左边。注意这里顺序不能乱
- 将运算结果再次入栈，不断这样运行遍历，最后栈里唯一的元素则是最终运算结果
- 其实这题和20. 有效的括号类似，只是这里是需要三个元素，两个数字遇到一个运算符，做一个消除的操作，合成了一个数字
3.2 代码
class Solution { public int evalRPN(String[] tokens) { Stack<Integer> stack=new Stack<>(); int temp1; int temp2; for(String s:tokens){ if("+".equals(s)){ temp1=stack.pop(); temp2=stack.pop(); stack.push(temp2+temp1); }else if("-".equals(s)){ temp1=stack.pop(); temp2=stack.pop(); stack.push(temp2-temp1); }else if("*".equals(s)){ temp1=stack.pop(); temp2=stack.pop(); stack.push(temp2*temp1); }else if("/".equals(s)){ temp1=stack.pop(); temp2=stack.pop(); stack.push(temp2/temp1); }else{ stack.push(Integer.valueOf(s)); } } return stack.pop(); } }
