No.1

题目

有效的括号

思路

• 奇数个符号一定不符合
• 分析括号不匹配的可能性
• 第一种情况，字符串里左方向的括号多余了 ，所以不匹配
  ![[brackets0.png]]
• 第二种情况，括号没有多余，但是 括号的类型没有匹配上
  ![[brackets1.png]]
• 第三种情况，字符串里右方向的括号多余了，所以不匹配
  ![[brackets2.png]]

代码

public boolean isValid(String s) {  
    Stack<Character> stack = new Stack<>();  
    if (s.length() % 2 != 0)  
        return false;  
    for (int i = 0; i < s.length(); i++) {  
        char item = s.charAt(i);  
        if (item == '(')  
            stack.push(')');  
        else if (item == '[')  
            stack.push(']');  
        else if (item == '{')  
            stack.push('}');  
        // 遍历的过程中栈已经清空了，说明右括号的部分多余了  
        // 栈顶元素和当前元素不一致，说明不合法  
        else if (stack.empty() || stack.peek() != item)  
            return false;  
        // 只剩下栈顶元素和当前元素相等的情况  
        else  
            stack.pop();  
    }  
  
    return stack.empty();  
}

No.2

题目

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

思路

• 遍历字符串，用栈
• 碰到和栈顶元素相同的，pop
• 遍历时的几种情况
  • 栈为空-入栈
  • 栈非空&栈顶元素不同-入栈
  • 栈非空&栈顶元素相同-出栈
• 最后把栈POP空，拼字符串，然后反转

代码

public String removeDuplicates(String s) {  
    Stack<Character> stack = new Stack<>();  
    StringBuilder sb = new StringBuilder();  
  
    for (int i = 0; i < s.length(); i++) {  
        char item = s.charAt(i);  
        if (stack.empty())  
            stack.push(item);  
        else if (!stack.empty() && item != stack.peek())  
            stack.push(item);  
        else if (!stack.empty() && item == stack.peek())  
            stack.pop();  
    }  
  
    Stack<Character> tempS = new Stack<>();  
    while (!stack.empty())  
        tempS.push(stack.pop());  
    while (!tempS.empty())  
        sb.append(tempS.pop());  
  
    return sb.toString();  
}

No.3

题目

逆波兰表达式求值

思路

• 栈
• 注意提取操作数的顺序，先pop的是左操作数，后pop的是右操作数

代码

public int evalRPN(String[] tokens) {  
    Stack<Integer> stack = new Stack<>(); // 操作数栈  
  
    for (int i = 0; i < tokens.length; i++) {  
        String item = tokens[i];  
        int op1, op2;  
  
        switch (item) {  
            case "+" -> {  
                op1 = stack.pop();  
                op2 = stack.pop();  
                stack.push(op1 + op2);  
            }  
            case "-" -> {  
                op2 = stack.pop();  
                op1 = stack.pop();  
                stack.push(op1 - op2);  
            }  
            case "*" -> {  
                op1 = stack.pop();  
                op2 = stack.pop();  
                stack.push(op1 * op2);  
            }  
            case "/" -> {  
                op2 = stack.pop();  
                op1 = stack.pop();  
                stack.push(op1 / op2);  
            }  
            default -> {  // 只剩下数字  
                int tmp = Integer.parseInt(item);  
                stack.push(tmp);  
            }  
        }  
    }  
  
    return stack.pop();  
}