代码随想录：栈与队列4-6

20.有效的括号

题目

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

代码

class Solution {
    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 == '('){
                stack.push(')');
            }
            else if(c == '{'){
                stack.push('}');
            }
            else if(c == '['){
                stack.push(']');
            }
            //如果是右括号，如果此时栈已经空了，说明右括号多了，返回false
            //如果是右括号,如果左右括号不匹配，返回false
            else if(stack.isEmpty() || c != stack.peek()){
                return false;
            }
            //左右括号匹配，栈顶元素出栈
            else{
                stack.pop();
            }
        }
        //如果结束后栈非空，说明左括号多了，也要return false
        return stack.isEmpty();
    }
}

总结

1.思想

要判断左右括号匹配，优先用栈来解决。

大致算法是，如果是左括号就让其进栈，如果是右括号就把栈顶元素取出来匹配一下，如果不匹配就返回false，匹配就把栈底元素出栈。不过要把所有不匹配的情况考虑清楚：

（1）第一种：左括号多，那么for循环结束之后的栈是非空的

（2）第二种：右括号多，那么遍历到右括号时栈已经是空了

（3）第三种就：左右括号数量匹配但是内容不匹配。

还有要想一下，如何做左右括号的匹配，其实就是让左括号进栈的时候，替换为对应的右括号就行。

2.算法流程

用for循环遍历字符串，如果当前元素是左括号“（、{、[ ”，就分别使用三个if分支语句，让其对应的右括号“）、}、] ”进栈。

如果当前元素已经不是上面3种左括号，已经是右括号了，要判断2种情况，如果此时的栈已经是空的，就代表右括号太多，要返回false，或者如果此时的左右括号不匹配，也要返回false。如果上面的情况都不满足，说明左右括号是匹配的，把栈顶元素pop出来。

最后，判断栈是否为空，看看左括号是不是太多了就行。

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

题目

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"

代码

class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();

        for(int i=0;i < s.length(); i++){
            char c = s.charAt(i);
            //如果栈是空的，或者栈不空但是栈顶元素！=当前元素
            if(stack.isEmpty() || stack.peek() != c){
                stack.push(c); //当前元素入栈
            }
            //如果栈非空，且栈顶元素==当前元素
            else{
                stack.pop(); //栈顶元素出栈
            }
        }

        StringBuilder sb = new StringBuilder();
        //把最终的栈元素从栈顶开始输出
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }

        //出栈顺序和我们要的结果相反，要把结果字符串反转一下再转为String类型
        return sb.reverse().toString();

    }
}

总结

1.思想

字符串删除重复元素也是一种变相的括号匹配问题。核心思路如下：

如果栈是空的或者栈顶元素和当前元素不相同，就把当前元素入栈。

如果栈顶元素等于当前元素，就把栈顶出栈。最后遍历完String后，栈内剩余的就是我们要的不重复的字符串。

2.算法流程

for循环遍历字符串，获取当前元素c，如果当前栈是空或者栈顶peek元素不等于c，就把当前元素c入栈push到栈中，如果栈顶peek元素等于c，就把栈顶元素pop出来。for循环结束后，栈中剩余的元素就是我们要的结果集，把他们一个个出栈存到字符串里就行。

3.注意点

由于最后结果集出栈的时候，出栈的字符顺序和我们要的是相反的，所以当栈不空时，可以循环用StringBuild逐个append出栈元素，最后再返回sb.reverse().toString()就行。

150.逆波兰表达式求值

题目

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

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

代码

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();

        for(String s : tokens){
            //如果是算法符合，就把栈顶的两个元素pop出来，计算后再push回去
            if(s.equals("+")){
                int x2 = stack.pop();
                int x1 = stack.pop();
                stack.push(x1 + x2);
            }
            else if(s.equals("-")){
                int x2 = stack.pop();
                int x1 = stack.pop();
                stack.push(x1 - x2);
            }
            else if(s.equals("*")){
                int x2 = stack.pop();
                int x1 = stack.pop();
                stack.push(x1 * x2);
            }
            else if(s.equals("/")){
                int x2 = stack.pop();
                int x1 = stack.pop();
                stack.push(x1 / x2);
            }
            //如果s不是算术符号，s是数字,就把s转为Integer再push进去
            else{
                stack.push(Integer.valueOf(s));
            }
        }
        //最后栈内的元素就是计算结果
        return stack.pop();
    }
}