📃 题目描述

题目链接：BM49 表达式求值 (opens new window)

🔔 解题思路

import java.util.*;
public class Solution {

    public int solve (String s) {
        // write code here
        char[] chars = s.toCharArray();
        Stack<Integer> stack = new Stack<>();

        int num = 0;
        // op 表示 num 前的符号
        char op = '+';

        for (int i = 0; i < chars.length; i ++) {
            char c = chars[i];
            // 整数可能不止一位
            if (c >= '0' && c <= '9') {
                num = num * 10 + (c - '0');
            }

            // '('
            else if (c == '(') {
                // 找到对应的 )，里面可能嵌套很多个 ()
                int j = i + 1;
                // ( 的数量
                int count = 1;
                while (count > 0 && j < chars.length) {
                    if (chars[j] == '(') {
                        count ++;
                    }
                    if (chars[j] == ')') {
                        count --;
                    }

                    j ++;
                }
                // 递归求 () 内的表达式
                num = solve(s.substring(i + 1, j - 1));
                i = j - 1;
            }

            // op
            if (!Character.isDigit(c) || i == chars.length - 1) {
                // 处理上一个运算符
                if (op == '+') {
                    stack.push(num);
                } else if (op == '-') {
                    stack.push(-num);
                } else if (op == '*') {
                    stack.push(num * stack.pop());
                } else if (op == '/') {
                    stack.push(stack.pop() / num);
                }

                // 更新当前运算符
                op = c;
                num = 0;
            }

        }

        int res = 0;
        while (!stack.isEmpty()) {
            res += stack.pop();
        }

        return res;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：