返回

[Leetcode]227. Basic Calculator II(C++)

题目描述

题目链接:227. Basic Calculator II

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

The integer division should truncate toward zero.

例子

例子 1

Input: s = "3+2*2" Output: 7

例子 2

Input: s = " 3/2 " Output: 1

例子 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.

解题思路

这道题由于包含了加减和乘除两种优先级的运算,因此我们可以通过一次迭代先完成所有乘除运算,再通过一次迭代完成所有加减的运算,具体思路如下:用一个栈存储所有的操作数,并且存储上一个遇到的操作符

  • 先遍历得出一个操作数
    • 如果栈为空,表明这是第一个操作数,直接压入栈中
    • 如果上一个操作符为 +-,不需要计算,压入栈中(如果是 - 则压入相反数)
    • 如果上一个操作符为 */ ,需要计算,从栈顶取出元素跟当前操作数进行相应操作,将结果压入栈中
  • 跳过空格,更新操作符

一次遍历后,栈中保存所有的操作数相加即可得到答案,代码如下:

#include <stack>
#include <string>

class Solution {
public:
    int calculate(std::string s) {
        std::stack<int> stk;
        int idx = 0;
        int result = 0;
        char prev_op = '+';
        while (idx < s.length()) {
            if (s[idx] == ' ') {
                idx++;
                continue;
            }

            if (std::isdigit(s[idx])) {
                int val = 0;
                while (idx < s.length() && std::isdigit(s[idx])) {
                    val *= 10;
                    val += s[idx] - '0';
                    idx++;
                }

                // first val
                if (stk.empty()) {
                    stk.push(val);
                    continue;
                }

                if (prev_op == '+') {
                    stk.push(val);
                } else if (prev_op == '-') {
                    stk.push(-val);
                } else if (prev_op == '*') {
                    stk.top() *= val;
                } else if (prev_op == '/') {
                    stk.top() /= val;
                }
            } else {
                prev_op = s[idx];
                idx++;
            }
        }

        while (!stk.empty()) {
            result += stk.top();
            stk.pop();
        }

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

GitHub 代码同步地址: 227.BasicCalculatorIi.cpp

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

Built with Hugo
Theme Stack designed by Jimmy