跳至主要內容

224. 基本计算器


224. 基本计算器

🔴   🔖  递归 数学 字符串  🔗 力扣open in new window LeetCodeopen in new window

题目

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逆波兰表达式求值[✓] 数组 数学🟠🀄️open in new window 🔗open in new window
227基本计算器 II[✓] 数学 字符串🟠🀄️open in new window 🔗open in new window
241为运算表达式设计优先级递归 记忆化搜索 数学 2+🟠🀄️open in new window 🔗open in new window
282给表达式添加运算符数学 字符串 回溯🔴🀄️open in new window 🔗open in new window
772基本计算器 III 🔒[✓] 递归 数学 1+🔴🀄️open in new window 🔗open in new window
2019解出数学表达式的学生分数 记忆化搜索 数组 3+🔴🀄️open in new window 🔗open in new window
2232向表达式添加括号后的最小结果字符串 枚举🟠🀄️open in new window 🔗open in new window