跳至主要內容

224. Basic Calculator

224. Basic Calculatoropen 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}
 */
/**
 * @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. 逆波兰表达式求值](https://leetcode.com/problems/evaluate-reverse-polish-notation)
- [227. 基本计算器 II](https://leetcode.com/problems/basic-calculator-ii)
- [241. 为运算表达式设计优先级](https://leetcode.com/problems/different-ways-to-add-parentheses)
- [282. 给表达式添加运算符](https://leetcode.com/problems/expression-add-operators)
- [🔒 Basic Calculator III](https://leetcode.com/problems/basic-calculator-iii)
- [2019. 解出数学表达式的学生分数](https://leetcode.com/problems/the-score-of-students-solving-math-expression)
- [2232. 向表达式添加括号后的最小结果](https://leetcode.com/problems/minimize-result-by-adding-parentheses-to-expression)
Copyright © 2024 2xiao