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

20.有效的括号

题目

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

有效字符串需满足：

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

代码

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();
    }
}

总结

1.思想

        逆波兰表达式就是把数字写前面，计算符号写后面的一种计算式。它的计算方法是，如果遇到计算符号，就把该计算符号的前两个数字用该符号进行计算，直到用完每一个计算符号。因此，我们可以用栈存储数字，遇到计算符号，就把栈顶的两个数字出栈计算，计算完再入栈。

2.算法流程

        遍历String数组，如果当前字符串s是“+”，就把栈顶的两个元素pop出来，用x2和x1存储，计算x1+x2结果，把x1+x2再push进栈。其他的“-”、“*”、“/”原理一样，再写三个else语句就行。

        如果当前字符串s是数字，就把s转为Integer整型后push到栈中。最后栈内的元素就是计算结果。

3.注意点

（1）出栈获取两个x1和x2计算时，第一个出栈元素是x2，第二个出栈元素是x1，计算时x1在前x2在后，不能反过来哦。

（2）这里的tokens是字符串数组，不是字符串，因此遍历时，有下面两种方式：

        ①用String进行增强for，写法是String s : tokens

        ②用普通的for，写法是for(int i=0; i < tokens.length; i++) ，然后String s = tokens[i];

如果是String字符串，而不是字符串数组，才能用下面这种写法：

4.语法点

（1）判断两个字符串是否相同，要用s1.equals(s2)。判断字符char是否相同，才能用==。

（2）把String转为Integer，用Integer i = Integer.valueOf(str)，注意O要大写。