224. 基本计算器

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

题目

Given a string s representing a valid expression, implement a basic 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 = " 2-1 + 2 "

Output: 3

Example 3:

Input: s = "(1+(4+5+2)-3)+(6+8)"

Output: 23

Constraints:

• 1 <= s.length <= 3 * 105
• s consists of digits, '+', '-', '(', ')', and ' '.
• s represents a valid expression.
• '+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
• '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
• There will be no two consecutive operators in the input.
• Every number and running calculation will fit in a signed 32-bit integer.

题目大意

实现一个基本的计算器来计算一个简单的字符串表达式的值。字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格 。

解题思路

• 加减法计算器，其实就是一个去括号的过程，需要根据 + - 和 ( )来判断数字的正负；
• 遍历字符串，每当遇到 ( ，就使用栈来保存括号前的运算符号；
• 注意，负负得正的情况需要特殊处理，所以需要记录每次计算出来的符号；
• 遇到 ） ，则出栈；
• 遇到 + -，则用 sign 来保存数字前的运算符号；
• 每个数字的正负都取决于 栈顶和数字前的运算符号的乘积，即：sum * sign * stack[stack.length - 1]；
• 将 数字 * 正负符号 累加起来即可；

代码

/**
 * @param {string} s
 * @return {number}
 */
var calculate = function (s) {
	let res = 0,
		sum = 0,
		sign = 1;
	let stack = [1];
	const isDigit = (str) => str <= '9' && str >= '0';
	for (let i of s) {
		if (isDigit(i)) sum = sum * 10 + Number(i);
		else {
			res += sum * sign * stack[stack.length - 1];
			sum = 0;
			if (i === '+') sign = 1;
			else if (i === '-') sign = -1;
			else if (i === '(') {
				stack.push(stack[stack.length - 1] * sign);
				sign = 1;
			} else if (i === ')') stack.pop();
		}
	}
	res += sum * sign;
	return res;
};

相关题目

题号	标题	题解	标签	难度
150	逆波兰表达式求值	[✓]	栈 数组 数学
227	基本计算器 II	[✓]	栈 数学 字符串
241	为运算表达式设计优先级		递归 记忆化搜索 数学 2+
282	给表达式添加运算符		数学 字符串 回溯
772	基本计算器 III 🔒	[✓]	栈 递归 数学 1+
2019	解出数学表达式的学生分数		栈 记忆化搜索 数组 3+
2232	向表达式添加括号后的最小结果		字符串 枚举