算法|20. 有效的括号、删除字符串中的所有相邻重复项、逆波兰表达式求值

一、 20. 有效的括号

题目链接：https://leetcode.cn/problems/valid-parentheses/
思路：遇到“( { [” 将对应的 ”)}]“的字符压入栈中，遇到”)}]“字符的时候，判断栈是否为空，为空直接俄返回false。或者不为空和栈顶的元素不相同也返回false，最后判断是栈是否为空

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(']');
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                if (stack.pop() != c) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

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

题目链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
思路一：使用栈结构，栈不为空并且栈顶元素和当前元素相等的话，就弹出栈顶元素，反之加入到栈中。然后遍历栈放入到str结果集中，注意栈是倒序的

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.pop();
            } else {
                stack.push(c);
            }
        }
        String result = "";
        while (!stack.isEmpty()) {
            result = stack.pop() + result;
        }
        return result;
    }
}

思路二、使用stringBuffer模拟栈,如果栈不为空，并且栈顶元素和当前元素相同，则弹出栈顶元素，反之，则加入元素

class Solution {
    public String removeDuplicates(String s) {
        StringBuffer result = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int len = result.length();
            if (len != 0 && result.charAt(len - 1) == c) {
                result.deleteCharAt(len - 1);
            } else {
                result.append(c);
            }
        }

        return result.toString();
    }
}

三、150. 逆波兰表达式求值

题目链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation/
思路：遇到+ - * / 字符串时候，stack.push(stack.pop() + stack.pop());注意 - /是前一个数-or/后一个数
遇到数字直接stack.push(数字);

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String str = tokens[i];
            if ("+".equals(str)) {
                stack.push(stack.pop() + stack.pop());
            } else if ("-".equals(str)) {
                int temp = stack.pop();
                stack.push(stack.pop() - temp);
            } else if ("*".equals(str)) {
                stack.push(stack.pop() * stack.pop());
            } else if ("/".equals(str)) {
                int temp = stack.pop();
                stack.push(stack.pop() / temp);
            } else {
                stack.push(Integer.parseInt(str));
            }
        }

        return stack.pop();
    }
}