LeetCode 772. 基本计算器 III

Categories:

题目描述
思路分析
1. 解法一：递归 + 栈（推荐）
相似题目

题目描述

✅ 772. 基本计算器 III

思路分析

解法一：递归 + 栈（推荐）

核心思路：

扫描字符串，遇到数字累积成 num。

遇到运算符或右括号时，根据上一个运算符把 num 入栈或与栈顶计算。

遇到 ( 递归求子表达式值。

遇到 ) 结束当前递归，汇总栈结果。

复杂度分析：

时间复杂度：O(n)，其中 n 表示表达式长度。

空间复杂度：O(n)，递归栈与辅助栈。

// 递归解析 + 栈计算
class Solution {
    public int calculate(String s) {
        int[] index = new int[1];
        return dfs(s.toCharArray(), index);
    }

    private int dfs(char[] ch, int[] index) {
        Deque<Integer> stack = new ArrayDeque<>();
        int num = 0;
        char sign = '+';

        while (index[0] < ch.length) {
            char c = ch[index[0]];
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            }
            if (c == '(') {
                index[0]++;
                num = dfs(ch, index);
            }
            if ((!Character.isDigit(c) && c != ' ') || index[0] == ch.length - 1) {
                if (sign == '+') {
                    stack.push(num);
                } else if (sign == '-') {
                    stack.push(-num);
                } else if (sign == '*') {
                    stack.push(stack.pop() * num);
                } else if (sign == '/') {
                    stack.push(stack.pop() / num);
                }
                sign = c;
                num = 0;
            }
            if (c == ')') {
                break;
            }
            index[0]++;
        }

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

// 递归解析 + 栈计算
func calculate(s string) int {
	idx := 0
	return dfsCalc(s, &idx)
}

func dfsCalc(s string, idx *int) int {
	stack := make([]int, 0)
	num := 0
	sign := byte('+')

	for *idx < len(s) {
		c := s[*idx]
		if c >= '0' && c <= '9' {
			num = num*10 + int(c-'0')
		}
		if c == '(' {
			*idx++
			num = dfsCalc(s, idx)
		}
		if (c < '0' || c > '9') && c != ' ' || *idx == len(s)-1 {
			switch sign {
			case '+':
				stack = append(stack, num)
			case '-':
				stack = append(stack, -num)
			case '*':
				stack[len(stack)-1] = stack[len(stack)-1] * num
			case '/':
				stack[len(stack)-1] = stack[len(stack)-1] / num
			}
			sign = c
			num = 0
		}
		if c == ')' {
			break
		}
		*idx++
	}

	res := 0
	for _, v := range stack {
		res += v
	}
	return res
}

相似题目

题目	难度	考察点
224. 基本计算器	困难	栈
227. 基本计算器 II	中等	栈
394. 字符串解码	中等	栈
150. 逆波兰表达式求值	中等	栈
772. 基本计算器 III	困难	栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/83573269