leetcode 栈部分笔记

1. 有效的括号

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

有效字符串需满足：

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

解题思路： 用栈存储左括号，如果遇到右括号，则先判断栈是否为空，如果为空则false，如果不为空，则弹栈判断是否匹配，如果不匹配则false。

class Solution {
    public boolean isValid(String s) {
        char[] chars = s.toCharArray();
        Stack<Character> stack = new Stack<Character>();
        for (char c : chars){
            if (c == '('||c == '['||c == '{'){
                stack.push(c);
            }
            if (c == ')'){
                if (stack.isEmpty()){
                    return false;
                }
                if (!stack.pop().equals('(')) {
                    return false;
                }
            }
            if (c == ']'){
                if (stack.isEmpty()){
                    return false;
                }
                if (!stack.pop().equals('[')) {
                    return false;
                }
            }
            if (c == '}'){
                if (stack.isEmpty()){
                    return false;
                }
                if (!stack.pop().equals('{')) {
                    return false;
                }
            }
        }
        if (!stack.isEmpty()){
            return false;
        }else {
            return true;
        }
    }
}

2. 简化路径

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/’ 开头），请你将其转化为 更加简洁的规范路径。

在 Unix 风格的文件系统中规则如下：

一个点 ‘.’ 表示当前目录本身。
此外，两个点 ‘…’ 表示将目录切换到上一级（指向父目录）。
任意多个连续的斜杠（即，‘//’ 或 ‘///’）都被视为单个斜杠 ‘/’。
任何其他格式的点（例如，‘…’ 或 ‘…’）均被视为有效的文件/目录名称。
返回的 简化路径 必须遵循下述格式：

始终以斜杠 ‘/’ 开头。
两个目录名之间必须只有一个斜杠 ‘/’ 。
最后一个目录名（如果存在）不能 以 ‘/’ 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘…’）。
返回简化后得到的 规范路径 。

解题思路： 首先用/分割所有字符串,对字符串数组进行遍历，如果是…，则返回上一级目录，也就是栈内最后一个元素弹出。如果不是点并且是个字符串，则放入栈中。如果stack不为空，则进行路径构造，也就是用/构造，再弹出第一个元素如此构造。

class Solution {
    public String simplifyPath(String path) {
        StringBuilder s = new StringBuilder();
        String[] sp = path.split("/");
        Deque<String> stack = new LinkedList<String>();
        for (String p : sp){
            if ("..".equals(p)){
                if (!stack.isEmpty()){
                    stack.pollLast();
                }
            }else if (p.length()>0&&!".".equals(p)){
                stack.offerLast(p);
            }
        }
        if (stack.isEmpty()){
            s.append('/');
        }else {
            while (!stack.isEmpty()){
                s.append('/');
                s.append(stack.pollFirst());
            }
        }
        return s.toString();
    }
}

3. 逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

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

解题思路： 首先定义计算逻辑。用栈解决，首先遍历整个字符串数组，判断是否为操作符，如果是操作符，则需要进行计算，先把栈中两个元素弹出，计算后，并把计算结果存入栈中。如果不是运算符，则直接把该字符串存入栈中。
注意：字符串转整数 Integer.parseInt()。

class Solution {
    public int caculate(int a, int b, char c) {
        int res = 0;
        switch (c) {
            case '+': res = a + b; break;
            case '-': res = a - b; break;
            case '*': res = a * b; break;
            case '/': res = a / b; break;
        }
        return res;
    }

    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<>();
        for (String token : tokens) {
            // 判断是否是操作符
            if ("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token)) {
                int b = stack.pollLast();
                int a = stack.pollLast();
                stack.offerLast(caculate(a, b, token.charAt(0)));
            } else {
                // 将数字字符串转换为整数并入栈
                stack.offerLast(Integer.parseInt(token));
            }
        }
        return stack.pollLast();
    }
}