772. 基本计算器 III

🔴   🔖  栈 递归 数学 字符串  🔗 LeetCode

题目

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, '+', '-', '*', '/' operators, and open '(' and closing parentheses ')'. The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2^31, 2^31 - 1].

calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = "1+1"

Output: 2

Example 2:

Input: s = "6-4/2"

Output: 4

Example 3:

Input: s = "2*(5+5*2)/3+(6/2+8)"

Output: 21

Constraints:

• 1 <= s <= 10^4
• s consists of digits, '+', '-', '*', '/', '(' and ')'.
• s represents a valid expression.

题目大意

实现一个基本的计算器来计算简单的表达式字符串。

表达式字符串只包含非负整数，算符 '+'、'-'、'*'、'/'、左括号 '(' 和右括号'）' 。整数除法需要 向下截断 。

你可以假定给定的表达式总是有效的。所有的中间结果的范围均满足 [-2^31, 2^31 - 1] 。

注意：你不能使用任何将字符串作为表达式求值的内置函数，比如 eval() 。

解题思路

这个问题与四则运算类似，涉及操作符优先级处理和括号表达式的递归计算。可以使用 栈 (stack) 来帮助处理表达式，并使用 递归 来处理括号中的子表达式。

1. 定义一个递归函数 helper 用于递归地遍历字符串，isDigit 辅助函数用于判断当前字符是否为数字。
2. 在递归函数 helper 中，使用一个栈 存储操作数。
3. 遍历表达式字符串：
   • 遇到数字时，计算整个数字（可能有多位）。
   • 遇到 +, - 时，低优先级，放入栈中，等其他优先级高的运算处理完再做加减法。
   • 遇到 *, / 时，高优先级，需要立即计算，并将结果更新到栈中。
   • 遇到左括号 ( 时，递归计算括号内的表达式，这样可以优先计算嵌套的表达式。
   • 遇到右括号 ) 时，跳出循环，返回当前子表达式的结果。
4. 最后将栈中的所有数字求和（因为乘除法已经处理了，只剩下加减法）。

复杂度分析

• 时间复杂度：O(n)，其中 n 是输入字符串的长度。每个字符在遍历过程中会被处理一次。
• 空间复杂度：O(n)，主要是栈的深度用于存储括号内的中间结果。

代码

/**
 * @param {string} s
 * @return {number}
 */
var calculate = function (s) {
	let i = 0;

	const helper = () => {
		let stack = [];
		let num = 0;
		let sign = '+';

		while (i < s.length) {
			let char = s[i];

			if (isDigit(char)) {
				num = num * 10 + parseInt(char); // 计算完整的数字
			}

			if (char === '(') {
				i++; // 跳过 '('
				num = helper(); // 递归计算括号内的表达式
			}

			if ((!isDigit(char) && char !== ' ') || i === s.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(Math.trunc(stack.pop() / num));
				}
				sign = char; // 更新当前符号
				num = 0; // 重置 num
			}

			if (char === ')') {
				break; // 结束当前括号的计算
			}

			i++;
		}

		return stack.reduce((a, b) => a + b, 0); // 返回当前栈中数字的总和
	};

	return helper();
};

// 辅助函数：判断字符是否为数字
const isDigit = (char) => {
	return char >= '0' && char <= '9';
};

相关题目

题号	标题	题解	标签	难度
224	基本计算器	[✓]	栈 递归 数学 1+
227	基本计算器 II	[✓]	栈 数学 字符串
770	基本计算器 IV		栈 递归 哈希表 2+
1597	根据中缀表达式构造二叉表达式树		栈 树 字符串 1+