有效的括号

题目链接

https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html

思路

考虑三种情况
1、左括号多
2、右括号多
3、括号不多不少但不匹配

     public boolean isValid(String s) {
    Stack<Character> stack = new Stack();
    int i = 0;
    while(i < s.length()) {
        if(s.charAt(i) == '(') {
            stack.push(')');
        } else if(s.charAt(i) == '{') {
            stack.push('}');
        } else if(s.charAt(i) == '[') {
            stack.push(']');
        } else if(stack.isEmpty() || stack.pop() != s.charAt(i)) {
            return false;
        }
        i++;
    }
    return stack.isEmpty();
}

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

题目链接

https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html

思路

和上一题差不多，比较简单

    public String removeDuplicates(String s) {
     Stack<Character> stack = new Stack();
    int i = 0;
    while(i < s.length()) {
        if(stack.isEmpty() || stack.peek() != s.charAt(i)) {
            stack.push(s.charAt(i));
        } else {
            stack.pop();
        }
        i++;
    }
    StringBuilder stringBuilder = new StringBuilder();
    while(!stack.isEmpty()) {
        stringBuilder.append(stack.pop());
    }
    return stringBuilder.reverse().toString();
}

逆波兰表达式求值

题目链接

https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html

思路

    public int evalRPN(String[] tokens) {
  Stack<Integer> stack = new Stack<>();
    for(String str : tokens) {
        if(str.equals("+")) {
            stack.push(stack.pop() + stack.pop());
        } else if(str.equals("-")) {
            stack.push(-stack.pop() + stack.pop());
        } else if (str.equals("*")) {
            stack.push(stack.pop() * stack.pop());
        } else if(str.equals("/")) {
            int t1 = stack.pop();
            int t2 = stack.pop();
            stack.push(t2/t1);
        } else {
            stack.push(Integer.valueOf(str));
        }

    }
    return stack.pop();
}