772. 基本计算器 III 🔒
772. 基本计算器 III 🔒
题目
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) 来帮助处理表达式,并使用 递归 来处理括号中的子表达式。
- 定义一个递归函数
helper
用于递归地遍历字符串,isDigit
辅助函数用于判断当前字符是否为数字。 - 在递归函数
helper
中,使用一个栈 存储操作数。 - 遍历表达式字符串:
- 遇到数字时,计算整个数字(可能有多位)。
- 遇到
+
,-
时,低优先级,放入栈中,等其他优先级高的运算处理完再做加减法。 - 遇到
*
,/
时,高优先级,需要立即计算,并将结果更新到栈中。 - 遇到左括号
(
时,递归计算括号内的表达式,这样可以优先计算嵌套的表达式。 - 遇到右括号
)
时,跳出循环,返回当前子表达式的结果。
- 最后将栈中的所有数字求和(因为乘除法已经处理了,只剩下加减法)。
复杂度分析
- 时间复杂度:
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+ |