Leetcoder Day10｜栈与队列part02（栈的应用）

语言：Java/C++

20. 有效的括号

1047. 删除字符串中的所有相邻重复项

150. 逆波兰表达式求值

今日总结

20. 有效的括号

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

由于栈的特殊性（FILO），很适合解决对称匹配类问题。括号匹配就是使用栈解决的经典问题。

因为我们的阅读习惯都是从左至右的，所以往往先出现的都是左括号，因此先设置一个匹配栈，用于存放应该与已经出现的左括号所匹配的右括号，并且，先出现的左括号对应的右括号类型往往是后出现的，这个情况非常适合栈的特点，先进后出。如输入的字符串为"{[()]}"第一个出现的是"{"因此我们在栈中存放一个"}"，并且它是这个字符串的最后一个字符。因为已经对应左括号将应该出现的右括号都放入栈中了，当遍历到第一个右括号字符时，开始进行出栈操作。

遇到匹配问题，首先要进行分类，找出可能出现的情况，对于本题会出现以下三种情况：

字符串里左方向的括号多余：字符串结束栈还不为空。
字符串里右方向的括号多余：栈为空时，字符串还没结束。
字符串里括号没有多余，但是不匹配：遍历字符串时，栈顶右括号与当前字符串所指的字符不匹配。

class Solution {
    public boolean isValid(String s) {
         Stack<Character> stack=new Stack<>(); 
         if(s.length() % 2==1) return false;
         for(int i=0; i<s.length();i++){
             char ch=s.charAt(i);
             //将与左括号匹配的右括号压入栈中
             if (ch=='{') stack.push('}');
             else if(ch=='(') stack.push(')');
             else if(ch=='[') stack.push(']');
             //若栈提前为空或当前字符不等于弹出来的右括号，则返回false
             else if (stack.isEmpty() || stack.peek()!= ch) return false;
             else stack.pop();
         }   
         //若字符串为空栈不为空
         return stack.isEmpty();
    }
}

⚠️ 在进行情况判断的时候，一定要记住是stack.peek()!= ch，而不是stack.pop()!=ch，否则会导致java.util.EmptyStackException 异常。因此已经进行了一次pop操作了。

1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

1 <= S.length <= 20000
S 仅由小写英文字母组成。

因为本题涉及两个相邻且相同，转换思路就是，如果字符串里存在对称的结构，我们就会进行删除，实际上跟上一题有效括号匹配的题思路是一样的。只不过在括号里我们要判断的是不匹配的情况，而这里我们要删除匹配的情况因此可以将字符串遍历，先判断再入栈，如果当前字符与栈顶元素相同，则把栈顶元素弹出，如果不等，则放入栈中。随后将栈中剩余的元素依次弹出再把字符串进行翻转返回即可。如果是Java，使用StringBuilder类的reverse()方法来翻转字符串。

⚠️使用栈的用时和内存都较高，因此使用ArrayDeque效率会更高，删除会更快而且节省了翻转操作。

//使用栈
class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<s.length();i++){
             char ch=s.charAt(i);
             if(stack.isEmpty()||stack.peek()!=ch) stack.push(ch);
             else stack.pop();
        }
        s = "";
        while(!stack.isEmpty()){
            s+=stack.pop(); 
        }
        StringBuilder sb = new StringBuilder();
        for(int i=s.length()-1;i>=0;i--){
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}

//使用deque

class Solution {
    public String removeDuplicates(String s) {
        ArrayDeque<Character> deque = new ArrayDeque<>();
        for(int i=0;i<s.length();i++){
             char ch=s.charAt(i);
             if(deque.isEmpty()||deque.peek()!=ch) deque.push(ch);
             else deque.pop();
        }
        s = "";
        while(!deque.isEmpty()){
            s+=deque.pollLast();
        }
        return s;
        
    }
}

优化的方法还可以拿字符串直接作为栈，省去了栈还要转为字符串的操作。这样的话设置一个指针top，指向字符串末尾元素，即栈顶。

class Solution {
    public String removeDuplicates(String s) {
        StringBuffer str=new StringBuffer();
        int top=-1; //设置一个指针指向栈顶，即字符串尾部
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(top>=0 && str.charAt(top)==ch){
                str.deleteCharAt(top);
                top--;
            }
            else{
                // 将当前元素接入字符串，top指向最后一个元素
                str.append(ch);
                top++;
            }
        }
        return str.toString();
        
    }
}

150. 逆波兰表达式求值

根据逆波兰表示法，求表达式的值。

逆波兰表达式：是一种后缀表达式，所谓后缀就是指运算符写在后面。

有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入: ["2", "1", "+", "3", " * "]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例2:
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。

根据逆波兰的第二个优点其实本题的做法就已经呼之欲出了，数据结构中，后缀表达式往往可以用后序二叉树展现出来。本题思路可以简化为，遇到一个符号则把符号前面的拿出来进行符号对应的操作再压入栈中，很像上一题相邻重复项的思路，只不过这里的重复项定义为数字。

⚠️本题有几个需要注意的语法事项：

这里的tokens定义的是数组类型，因此不能用length()方法来提取长度而是使用length
在进行减法操作时，不能简单的使用deque.pop() - deque.pop()，不然如下图会变成’3-4‘，因为这个是栈，遵守先进后出原则，减数应该在被减数前被弹出来的，所以要用- deque.pop()+deque.pop()才可以表达‘4-3’的结果。
同理，除法操作也应该注意。
将数字存入栈时，应该注意转换为整型

class Solution {
    public int evalRPN(String[] tokens) {
        ArrayDeque<Integer> deque=new ArrayDeque<>();
        for (int i = 0; i < tokens.length; i++) {
            String ch = tokens[i];
            if(ch.equals("+")) deque.push(deque.pop() + deque.pop());
            //因为是栈，被减数是在减数后被弹出的
            else if(ch.equals("-")) deque.push(-deque.pop() + deque.pop());
            else if(ch.equals("*")) deque.push(deque.pop() * deque.pop());
            else if(ch.equals("/")) {
                int temp1 = deque.pop();//因为是栈，被除数是在除数后被弹出的
                int temp2 = deque.pop();
                deque.push(temp2 / temp1);
            }
            else deque.push(Integer.valueOf(ch));
        }
        return deque.pop();
    }
}