0%

[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.

解题思路

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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