题目描述
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