题目描述
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含非负整数,+
, -
,*
,/
四种运算符和空格 。 整数除法仅保留整数部分。
样例1
输入: "3+2*2"
输出: 7
样例2
输入: " 3/2 "
输出: 1
样例3
输入: " 3+5 / 2 "
输出: 5
说明
-
你可以假设所给定的表达式都是有效的。
-
请不要使用内置的库函数
eval
。
算法1
(栈模拟) $O(n)$
本题不包含括号,对于四个运算符加减乘除,我们可以将减号看成是数字前的负号,这样就只剩下了加号和乘除号,而对于乘除号则可以在扫描过程中直接计算出来并将中间结果保存,这样扫描完后只需要做加法就行了。具体做法是可以开一个栈记录中间结果和扫描得到的数字,以及一个变量sign
记录上一个运算符,当遇到一个操作符时我们计算上一个运算符。这样遍历完字符串后再对栈中的数字求和就是答案了。
另外我们在字符串结尾的时候还需要对上一个操作符进行一次运算,这里为了方便我们可以直接在字符串末尾补上任意一个操作符。
C++ 代码
class Solution {
public:
int calculate(string s) {
stack<int> nums;
int num = 0;
char sign = '+';
s += '+';
for (int i = 0; i < s.size(); i ++ ) {
if (isdigit(s[i])) num = num * 10 + (s[i] - '0');
if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
if (sign == '+') {
nums.push(num);
} else if (sign == '-') {
nums.push(-num);
} else if (sign == '*') {
int n = nums.top();
nums.pop();
nums.push(n * num);
} else if (sign == '/') {
int n = nums.top();
nums.pop();
nums.push(n / num);
}
num = 0;
sign = s[i];
}
}
int res = 0;
while (nums.size()) {
res += nums.top();
nums.pop();
}
return res;
}
};
算法2
(栈模拟) $O(n)$
同样是栈模拟,不过不同于算法1中对减法变加法并且最后计算加法的思路,我们也可以在扫描过程中直接计算加减法。首先我们用两个栈,一个数字栈保存数字和中间结果,一个符号栈保存遇到的操作符,然后我们是在遇见操作数的时候对表达式进行求值。比如对于"1 + 2 * 3"
我们遇见2
的时候不能先计算栈顶的加号,因为并不能确定后面还有没有优先级更高的乘除号,但是对于"1 + 2 + 3 * 4"
,我们遇见3
前面的+
号的时候我们就确定可以计算1 + 2
了。
总结起来就是当遇到运算符时,只要栈顶符号的优先级不低于新符号,就不断取出栈顶并输出,最后把新符号进栈。优先级为乘除 > 加减 > 左括号。
这里可以直接用 AcWing 3302. 表达式求值 的模板。
C++ 代码
class Solution {
public:
stack<int> num;
stack<char> op;
void eval() {
auto b = num.top(); num.pop();
auto a = num.top(); num.pop();
auto c = op.top(); op.pop();
int x;
if (c == '+') x = a + b;
else if (c == '-') x = a - b;
else if (c == '*') x = a * b;
else x = a / b;
num.push(x);
}
int calculate(string s) {
unordered_map<char, int> pr{{'(', 0}, {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
for (int i = 0; i < s.size(); i++) {
auto c = s[i];
if (c == ' ') continue;
if (isdigit(c)) {
int x = 0, j = i;
while (j < s.size() && isdigit(s[j]))
x = x * 10 + (s[j++] - '0');
i = j - 1;
num.push(x);
} else if (c == '(') {
op.push(c);
} else if (c == ')') {
while (op.top() != '(') eval();
op.pop();
} else {
while (op.size() && pr[op.top()] >= pr[c]) eval();
op.push(c);
}
}
while (op.size()) eval();
return num.top();
}
};