返回

[Leetcode]224. Basic Calculator(C++)

题目描述

题目链接:224. Basic Calculator

Given a string s representing an expression, implement a basic calculator to evaluate it.

例子

例子 1

Input: s = "1 + 1" Output: 2

例子 2

Input: s = " 2-1 + 2 " Output: 3

例子 3

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

Follow Up

Note

Constraints

  • 1 <= s.length <= 3 * 10^5
  • s consists of digits, '+', '-', '(', ')', and ' '.
  • s represents a valid expression.

解题思路

如果等式中没有等号的话那就很简单,只需要按照顺序:遍历数字作为第一个操作数 –> 取操作符设定下一个数字的符号 –> 遍历数字作为第二个操作数(乘上相应符号),并且和第一个数字进行相加作为下一次操作的第一个操作数,以此类推即可。在有括号时则改变了我们的操作顺序,我们可以做以下修改:

  • 初始化一个数字 result 作为当前(局部)总和,初始化符号为 sign = 1
  • 如果遇到数字,则遍历数字然后乘上相应的符号加在局部和中
  • 遇到 '+' 或者 '-',则更新符号 sign
  • 遇到 (:表示我们需要先计算括号后的结果再对当前局部和进行更新,因此将当前局部和以及符号压入一个栈中,并且重置局部和和符号用于括号内计算
  • 遇到 ):表示括号内计算已结束,将当前局部和用之前计算的方法更新到上一个局部和中,上一个局部和以及相应的操作在栈顶中

代码如下:

#include <stack>
#include <string>

class Solution {
public:
    int calculate(std::string s) {
        std::stack<int> stk;
        int result = 0;
        int sign = 1;
        int idx = 0;
        while (idx < s.length()) {
            if (std::isdigit(s[idx])) {
                int num = 0;
                while (idx < s.length() && std::isdigit(s[idx])) {
                    num *= 10;
                    num += (s[idx] - '0');
                    idx++;
                }
                result += sign * num;
                idx--;
            } else if (s[idx] == '+') {
                sign = 1;
            } else if (s[idx] == '-') {
                sign = -1;
            } else if (s[idx] == '(') {
                // use the top of stack as initial result and continue
                // computation
                stk.push(result);
                stk.push(sign);
                result = 0;
                sign = 1;
            } else if (s[idx] == ')') {
                result *= stk.top();
                stk.pop();
                result += stk.top();
                stk.pop();
            }
            idx++;
        }

        return result;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 224.BasicCalculator.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Built with Hugo
Theme Stack designed by Jimmy