227. 基本计算器 II

🟠   🔖  栈 数学 字符串  🔗 LeetCode

题目

Given a string s which represents an expression, evaluate this expression and return its value.

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].

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

Example 1:

Input: s = "3+2*2"

Output: 7

Example 2:

Input: s = " 3/2 "

Output: 1

Example 3:

Input: s = " 3+5 / 2 "

Output: 5

Constraints:

• 1 <= s.length <= 3 * 10^5
• s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
• s represents a valid expression.
• All the integers in the expression are non-negative integers in the range [0, 2^31 - 1].
• The answer is guaranteed to fit in a 32-bit integer.

题目大意

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

整数除法仅保留整数部分。

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

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

解题思路

1. 使用栈：

   • 采用栈来存储计算过程中间的结果。
   • 遇到乘法和除法时立即计算并将结果放入栈中；遇到加法和减法时，先将当前数字压入栈中，后续处理。

2. 遍历字符串：

   • 遍历输入字符串，逐个字符处理：
     • 当遇到数字时，构建完整的数字（可能是多位数）。
     • 当遇到操作符时，根据上一个操作符决定如何处理栈。
     • 注意处理空格，确保只在遇到有效操作符时进行处理。

3. 处理操作符：

   • 使用一个变量来记录当前操作符。根据当前操作符的类型，决定是将当前数字推入栈中、还是执行乘法或除法。

4. 最后计算结果：

   • 遍历完字符串后，栈中会存储所有的结果。最终只需将栈中的所有数字相加。

复杂度分析

• 时间复杂度：O(n)，其中 n 是输入字符串的长度。需要遍历字符串一次。
• 空间复杂度：O(n)，用于存储栈中间结果。

代码

/**
 * @param {string} s
 * @return {number}
 */
var calculate = function (s) {
	const isDigit = (char) => char >= '0' && char <= '9';
	let stack = [],
		sum = 0,
		operation = '+'; // 初始操作符
	for (let i = 0; i < s.length; i++) {
		let char = s[i];

		// 如果是数字，构建完整的数字
		if (isDigit(char)) {
			sum = sum * 10 + Number(char);
		}

		// 跳过空格
		if (char == ' ' && i < s.length - 1) {
			continue;
		}

		// 如果是操作符或者到达字符串末尾
		if (['+', '-', '*', '/'].includes(char) || i === s.length - 1) {
			if (operation == '+') {
				stack.push(sum);
			} else if (operation == '-') {
				stack.push(-sum);
			} else if (operation == '*') {
				stack.push(stack.pop() * sum);
			} else if (operation == '/') {
				stack.push((stack.pop() / sum) | 0);
			}
			// 更新当前操作符
			operation = char;
			sum = 0;
		}
	}
	return stack.reduce((a, b) => a + b, 0);
};

相关题目

题号	标题	题解	标签	难度
224	基本计算器	[✓]	栈 递归 数学 1+
282	给表达式添加运算符		数学 字符串 回溯
772	基本计算器 III	[✓]	栈 递归 数学 1+