LeetCode（54）基本计算器【栈】【困难】

链接： 基本计算器

1.题目

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = "1 + 1"
输出：2

示例 2：

输入：s = " 2-1 + 2 "
输出：3

示例 3：

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

提示：

• 1 <= s.length <= 3 * 10^5
• s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
• s 表示一个有效的表达式
• ‘+’ 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
• ‘-’ 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
• 输入中不存在两个连续的操作符
• 每个数字和运行的计算将适合于一个有符号的 32位 整数

---

2.答案

class Solution {
    public int calculate(String s) {
        s = s.replace(" ", "");
        char[] chars = s.toCharArray();
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            if (Arrays.asList('+', '-', '(').contains(c)) {
                stack.push(String.valueOf(c));
            } else if (c == ')') {
                List<String> subList = new ArrayList<>();
                while (!"(".equals(stack.peek())) {
                    subList.add(stack.pop());
                }
                stack.pop();
                String num = subList.get(subList.size() - 1);
                for (int j = subList.size() - 2; j >= 0; j--) {
                    String operator = subList.get(j--);
                    String numRight = subList.get(j);
                    num = operate(operator, num, numRight);
                }
                // 判断前面是否有一元操作符-
                boolean isNegative = stack.size() == 1 && "-".equals(stack.peek()) ||
                        stack.size() > 1 && "(".equals(stack.get(stack.size() - 2)) && "-".equals(stack.peek());
                if (isNegative) {
                    int number = Integer.parseInt(num);
                    if (number < 0) {
                        // --得+
                        stack.pop();
                        stack.push(String.valueOf(-1 * number));
                    } else {
                        stack.push(stack.pop() + num);
                    }
                } else {
                    stack.push(num);
                }
            } else if (c >= '0' && c <= '9') {
                boolean isNumber = stack.size() > 0 && isNumber(stack.peek());
                // 判断前面是否有一元操作符-
                boolean isNegative = stack.size() == 1 && "-".equals(stack.peek()) ||
                        stack.size() > 1 && "(".equals(stack.get(stack.size() - 2)) && "-".equals(stack.peek());
                if (isNumber || isNegative) {
                    stack.push(stack.pop() + c);
                } else {
                    stack.push(String.valueOf(c));
                }
            }
        }

        String num = stack.get(0);
        for (int j = 1; j < stack.size(); j++) {
            String operator = stack.get(j++);
            String numRight = stack.get(j);
            num = operate(operator, num, numRight);
        }
        return Integer.parseInt(num);
    }

    private String operate(String operator, String numLeft, String numRight) {
        switch (operator) {
            case "+": return String.valueOf(Integer.parseInt(numLeft) + Integer.parseInt(numRight));
            case "-": return String.valueOf(Integer.parseInt(numLeft) - Integer.parseInt(numRight));
            default:
                System.out.println("operate() error, operator: " + operator);
                return "0";
        }
    }

    private boolean isNumber(String s) {
        return s.matches("-?[0-9]+");
    }
}

---

3.提交结果截图

整理完毕，完结撒花~ 🌻