力扣刷题篇之栈与队列3

系列文章目录

前言

本系列是个人力扣刷题汇总，本文是栈与队列。刷题顺序按照[力扣刷题攻略] Re：从零开始的力扣刷题生活 - 力扣（LeetCode）

一、表达式求值

150. 逆波兰表达式求值 - 力扣（LeetCode）

方法一，用栈

把数字都入栈，遇到运算符号就弹出两数进行相应计算，

这里需要注意，如果是除法，先弹出来的数是除数，后弹出的才是被除数。

class Solution {
    public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList();
        for (String s : tokens) {
            if ("+".equals(s)) {       
                stack.push(stack.pop() + stack.pop());    
            } else if ("-".equals(s)) {
                stack.push(-stack.pop() + stack.pop());
            } else if ("*".equals(s)) {
                stack.push(stack.pop() * stack.pop());
            } else if ("/".equals(s)) {
                int temp1 = stack.pop();
                int temp2 = stack.pop();
                stack.push(temp2 / temp1);
            } else {
                stack.push(Integer.valueOf(s));
            }
        }
        return stack.pop();
    }
//     int pos = 0;

//     public int evalRPN(String[] tokens) {
//         this.pos = tokens.length - 1;
//         return eval(tokens);
//     }

//     public int eval(String[] tokens) {
//         String token = tokens[pos];
//         if (token.equals("*")) {
//             pos--;
//             return eval(tokens) * eval(tokens);
//         }
//         if (token.equals("+")) {
//             pos--;
//             return eval(tokens) + eval(tokens);
//         }
//         if (token.equals("/")) {
//             pos--;
//             int op = eval(tokens);
//             return eval(tokens) / op;
//         }
//         if (token.equals("-")) {
//             pos--;
//             int op = eval(tokens);
//             return eval(tokens) - op;
//         }
//         pos--;
//         return Integer.parseInt(token);
//     }
 }

方法二，用递归，有点不好理解。

通过递归的方式，从逆波兰表达式的最后一个元素开始，根据操作符进行相应的计算。在递归的过程中，通过不断改变 pos 指针的位置，实现对逆波兰表达式的深度优先遍历。

class Solution {
    int pos = 0;

    // 主函数，接受逆波兰表达式的字符串数组
    public int evalRPN(String[] tokens) {
        // 初始化位置指针
        this.pos = tokens.length - 1;
        // 调用递归函数进行表达式计算
        return eval(tokens);
    }

    // 递归函数，根据当前位置的操作符进行计算
    public int eval(String[] tokens) {
        // 获取当前位置的操作符或操作数
        String token = tokens[pos];
        
        // 根据操作符进行相应的计算
        if (token.equals("*")) {
            pos--;
            // 递归计算乘法操作
            return eval(tokens) * eval(tokens);
        }
        if (token.equals("+")) {
            pos--;
            // 递归计算加法操作
            return eval(tokens) + eval(tokens);
        }
        if (token.equals("/")) {
            pos--;
            // 递归计算除法操作
            int op = eval(tokens);
            return eval(tokens) / op;
        }
        if (token.equals("-")) {
            pos--;
            // 递归计算减法操作
            int op = eval(tokens);
            return eval(tokens) - op;
        }
        // 如果是操作数，将其转换为整数并返回
        pos--;
        return Integer.parseInt(token);
    }
}

224. 基本计算器 - 力扣（LeetCode）

方法一，用栈

只有加减法，于是用sign代表正负，然后要正确处理多位数的情况以及有括号的情况。

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        // sign 代表正负
        int sign = 1, res = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {
                int cur = ch - '0';
                while (i + 1 < length && Character.isDigit(s.charAt(i + 1)))
                    cur = cur * 10 + s.charAt(++i) - '0';
                res = res + sign * cur;
            } else if (ch == '+') {
                sign = 1;
            } else if (ch == '-') {
                sign = -1;
            } else if (ch == '(') {
                stack.push(res);
                res = 0;
                stack.push(sign);
                sign = 1;
            } else if (ch == ')') {
                res = stack.pop() * res + stack.pop();
            }
        }
        return res;
    }
}

方法二、递归，回溯

使用回溯法，递归地解析并计算表达式。它从左到右遍历输入字符串，根据不同的字符类型执行不同的操作。

class Solution {
   
    public int calculate(String s) {
        char[] cs = s.toCharArray();
        this.len = cs.length;
        // 调用回溯函数，从字符串的第一个字符开始计算
        return backTrack(cs, 0)[0];
    }
    
    int len;  // 字符串长度

    // 回溯函数，用于解析并计算表达式
    // 返回数组，元素1表示区间和，元素2表示区间的右边界
    public int[] backTrack(char[] cs, int p) {
        char c = ' ';
        char op = '+';  // 初始操作符设为'+'
        int res = 0;    // 初始结果为0
        int num = 0;    // 用于记录当前数字的值

        for (int i = p; i < len; ++i) {
            c = cs[i];
            
            // 如果字符是数字，则更新num
            if (c >= '0' && c <= '9') {
                num = num * 10 + c - '0';
            } else if (c == '+' || c == '-') {
                // 如果字符是'+'或'-'，更新结果和操作符，并将num清零
                res = (op == '+') ? res + num : res - num;
                op = c;
                num = 0;
            } else if (c == '(') {
                // 如果字符是'('，递归调用回溯函数处理括号内的表达式
                int[] sub = backTrack(cs, i + 1);
                num = sub[0];
                // 更新边界
                i = sub[1];
            } else if (c == ')') {
                // 如果字符是')'，返回当前结果和右边界
                res = (op == '+') ? res + num : res - num;
                return new int[]{res, i};
            }
        }
        
        // 处理最后一个数字
        res = (op == '+') ? res + num : res - num;
        return new int[]{res, len};
    }
}

227. 基本计算器 II - 力扣（LeetCode）

栈这个地方要说一下，

Deque（双端队列）和 Stack 都可以用来实现栈的功能。在 Java 中，Deque 接口提供了用于栈操作的方法，同时也提供了队列的操作。Stack 类则是 Vector 类的一个子类，专门用于实现栈。

推荐使用 Deque，因为它提供了更丰富的方法，而 Stack 则是基于 Vector，使用时需要注意线程安全性。Deque 在 Java 中自 Java 6 引入，并在 Java 7 中进行了进一步的优化。

看回这个题，方法一，用栈

class Solution {
    public int calculate(String s) {
        // 保存上一个符号，初始为 +
        char sign = '+';
        Stack<Integer> numStack = new Stack<>();
        // 保存当前数字，如：12是两个字符，需要进位累加
        int num = 0;
        int result = 0;
        for(int i = 0; i < s.length(); i++){
            char cur = s.charAt(i);
            if(cur >= '0'){
                // 记录当前数字。先减，防溢出
                num = num*10 - '0' + cur;
            }
            if((cur < '0' && cur !=' ' )|| i == s.length()-1){
                // 判断上一个符号是什么
                switch(sign){
                    // 当前符号前的数字直接压栈
                    case '+': numStack.push(num);break;
                    // 当前符号前的数字取反压栈
                    case '-': numStack.push(-num);break;
                    // 数字栈栈顶数字出栈，与当前符号前的数字相乘，结果值压栈
                    case '*': numStack.push(numStack.pop()*num);break;
                    // 数字栈栈顶数字出栈，除于当前符号前的数字，结果值压栈
                    case '/': numStack.push(numStack.pop()/num);break;
                }
                // 记录当前符号
                sign = cur;
                // 数字清零
                num = 0;
            }
        }
        // 将栈内剩余数字累加，即为结果
        while(!numStack.isEmpty()){
            result += numStack.pop();
        }
        return result;
    }
}

方法二、

class Solution {
    public int calculate(String s) {
        int[] oprands = new int[4];
        calculate(oprands, 0, '+');
        int num = 0;
        for(char c:s.toCharArray()){
            switch(c){
            case '+':
            case '-':
            case '*':
            case '/':
                calculate(oprands, num, c); num = 0; break;
            default:
                if ('0'<=c && c<='9'){
                    num = num*10 + c -'0';
                }
            }
        }
        calculate(oprands, num, '+');
        calculate(oprands, 0, '+');
        return oprands[0];
    }

    //0*1+ 2+
    //1-2* 2* -7+0+ 0+
    //1*2* 2-
    //1*2- 2*
    //

    //0+1-
    //0123
    private void calculate(int[] oprands, int num, int op){
        if (oprands[3]=='*'){
            oprands[2] *= num;
        }else if (oprands[3]=='/'){
            oprands[2] /= num;
        }else{
            switch(oprands[1]){
            case '+':
                oprands[0] += oprands[2]; break;
            case '-':
                oprands[0] -= oprands[2]; break;
            case '*':
                oprands[0] *= oprands[2]; break;
            case '/':
                oprands[0] /= oprands[2]; break;
            }
            oprands[1] = oprands[3];
            oprands[2] = num;
        }
        oprands[3] = op;
    }
}

772. 基本计算器 III - 力扣（LeetCode）

会员题，之后做

770. 基本计算器 IV - 力扣（LeetCode）

class Solution {
    private HashMap<String, Integer> map;
    private Deque<List<Item>> numbers;
    private Deque<Character> operators;
    private int index, size;

    public List<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
        map = new HashMap<>();
        for (int i = 0; i < evalvars.length; i++) {
            map.put(evalvars[i], evalints[i]);
        }
        numbers = new ArrayDeque<>();
        operators = new ArrayDeque<>();
        index = 0;
        size = expression.length();
        List<Item> items = calculate(expression);
        List<String> list = new ArrayList<>();
        for (Item item : items) {
            list.add(item.toString());
        }
        return list;
    }

    List<Item> calculate(String expression) {
        while (index < size) {
            char c = expression.charAt(index++);
            if (c == ' ') {
                continue;
            } else if (Character.isDigit(c)) {
                List<Item> list = new ArrayList<>();
                addList(list, getDigit(expression, c), new ArrayList<>());
                numbers.addLast(list);
            } else if (Character.isLowerCase(c)) {
                addListByName(expression, c);
            } else if (c == '(') {
                operators.addLast(c);
            } else {
                if (c == '*') {
                    if (!operators.isEmpty() && operators.peekLast() == '*') {
                        computeOnce();
                    }
                    operators.addLast(c);
                } else {
                    while (!operators.isEmpty() && operators.peekLast() != '(') {
                        computeOnce();
                    }
                    if (c == ')') {
                        operators.pollLast();
                    } else {
                        operators.addLast(c);
                    }
                }
            }
        }
        while (!operators.isEmpty()) {
            computeOnce();
        }
        return numbers.peek();
    }

    void computeOnce() {
        char operator = operators.pollLast();
        List<Item> items2 = numbers.pollLast();
        List<Item> items1 = numbers.pollLast();
        if (operator == '+') {
            numbers.addLast(add(items1, items2));
        } else if (operator == '-') {
            numbers.addLast(subtract(items1, items2));
        } else {
            numbers.addLast(multiply(items1, items2));
        }
    }

    void addListByName(String expression, char c) {
        List<Item> list = new ArrayList<>();
        String name = getName(expression, c);
        if (map.containsKey(name)) {
            addList(list, map.get(name), new ArrayList<>());
        } else {
            List<String> temp = new ArrayList<>();
            temp.add(name);
            list.add(new Item(1, temp));
        }
        numbers.addLast(list);
    }

    void addList(List<Item> list, int coef, List<String> vars) {
        if (coef != 0) {
            list.add(new Item(coef, vars));
        }
    }

    String getName(String expression, char c) {
        StringBuilder sb = new StringBuilder().append(c);
        while (index < size) {
            c = expression.charAt(index);
            if (!Character.isLowerCase(c)) {
                break;
            }
            sb.append(c);
            index++;
        }
        return sb.toString();
    }

    int getDigit(String expression, char c) {
        int digit = c - '0';
        while (index < size) {
            c = expression.charAt(index);
            if (!Character.isDigit(c)) {
                break;
            }
            digit = 10 * digit + c - '0';
            index++;
        }
        return digit;
    }

    List<Item> add(List<Item> items1, List<Item> items2) {
        List<Item> list = new ArrayList<>();
        int size1 = items1.size(), size2 = items2.size();
        for (int i = 0, j = 0; i < size1 || j < size2; ) {
            if (i == size1) {
                list.add(items2.get(j++));
            } else if (j == size2) {
                list.add(items1.get(i++));
            } else {
                Item item1 = items1.get(i), item2 = items2.get(j);
                int diff = item1.compareTo(item2);
                if (diff == 0) {
                    addList(list, item1.coef + item2.coef, item1.vars);
                    i++;
                    j++;
                } else if (diff > 0) {
                    list.add(item1);
                    i++;
                } else {
                    list.add(item2);
                    j++;
                }
            }
        }
        return list;
    }

    List<Item> subtract(List<Item> items1, List<Item> items2) {
        for (Item item : items2) {
            item.coef = -item.coef;
        }
        return add(items1, items2);
    }

    List<Item> multiply(List<Item> items1, List<Item> items2) {
        List<Item> list = new ArrayList<>();
        for (Item item1 : items1) {
            List<Item> items = new ArrayList<>();
            for (Item item2 : items2) {
                items.add(item1.multiply(item2));
            }
            list = add(list, items);
        }
        return list;
    }

    static class Item {
        int coef;
        List<String> vars;

        public Item(int coef, List<String> vars) {
            this.coef = coef;
            this.vars = vars;
        }

        Item multiply(Item item) {
            List<String> temp = new ArrayList<>();
            temp.addAll(vars);
            temp.addAll(item.vars);
            Collections.sort(temp);
            Item product = new Item(coef * item.coef, temp);
            return product;
        }

        int compareTo(Item item) {
            int diff = vars.size() - item.vars.size();
            if (diff != 0) {
                return diff;
            }
            List<String> temp = item.vars;
            for (int i = 0; i < vars.size(); i++) {
                diff = temp.get(i).compareTo(vars.get(i));
                if (diff != 0) {
                    break;
                }
            }
            return diff;
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append(coef);
            for (String name : vars) {
                builder.append('*').append(name);
            }
            return builder.toString();
        }
    }
}