专题: Calculator

作者 Lucyyang 日期 2020-04-16
专题: Calculator

Be more patient!

之前在准备AI Lab的面试,因此咕了博客很久啦,四月份已经过半了,得加把油呀!BTW,还是很幸运的拿到了字节跳动AI Lab的offer,而且居然被大佬面试了,希望这次实习能顺顺利利做下去,有一个好的产出啊!加油呀,Lucyyang!

Leetcode上有一系列的Calculator的题目,主要还是运用栈的结构去实现,现在就从简到难一一进行分析。

Calculate I

题目:LC227这个是没有括号的版本,即只有+,-,*,/四种运算,以及空格的情况。

方法:先只考虑有+,-的情况,那么关键问题就是一般我们都是X+5,X-5,5前面跟着的是符号,可以表示为符号后接数字的形式。但遇到第一个数是5+x的时候,其实也表示的是+5。那我们就先预设符号为+,然后与第一个数字5再组合成+5放入栈中。那如何处理第一个符号为-5的情况呢?我们可以预设第一个数字为0,如果第一个是-5,那就先放入+0,再放入-5。如果第一个是5,则直接把数字置为5后与+号一起放入栈中。先看下只有+、-时的代码。

int calculate(string s) {
stack<int> stk; // 存入栈中
// 初始化重点
int num = 0;
char sign = '+';
for (int i = 0; i < s.size(); i++) {
char c = s[i];
// 如果是数字,连续读取到 num
if (isdigit(c))
num = 10 * num + (c - '0');
// 如果不是数字,就是遇到了下一个符号,
// 之前的数字和符号就要存进栈中
// 注意空格处理
if ((!isdigit(c) && c != ' ') || i == s.size() - 1) {
switch (sign) {
case '+':
stk.push(num); break;
case '-':
stk.push(-num); break;
}
// 完成一次push后,重新赋值开始下一轮
sign = c;
num = 0;
}
}
// 将栈中所有结果求和就是答案
int res = 0;
while (!stk.empty()) {
res += stk.top();
stk.pop();
}
return res;
}

那有了*和\怎么办呢,例如x*5?那就只用把栈顶的数字x弹出来,与*5进行运算后再将结果放入栈中即可。注意有个坑:不可以在switch语句里定义变量!!!

代码:

int calculate(string s) {
stack<int> stk; // 存入栈中
// 初始化重点
int num = 0;
char sign = '+';
for (int i = 0; i < s.size(); i++) {
char c = s[i];
// 如果是数字,连续读取到 num
if (isdigit(c))
num = 10 * num + (c - '0');
// 如果不是数字,就是遇到了下一个符号,
// 之前的数字和符号就要存进栈中
// 注意空格处理
if ((!isdigit(c) && c != ' ') || i == s.size() - 1) {
int tmp = 0;
switch (sign) {
case '+':
stk.push(num); break;
case '-':
stk.push(-num); break;
case '*':
tmp = stk.top();
stk.pop();
stk.push(tmp*num);break;
case '/':
tmp = stk.top();
stk.pop();
stk.push(tmp/num);break;
}
// 完成一次push后,重新赋值开始下一轮
sign = c;
num = 0;
}
}
// 将栈中所有结果求和就是答案
int res = 0;
while (!stk.empty()) {
res += stk.top();
stk.pop();
}
return res;
}

Calculator II

题目:LC224,这道题目是只有+,-和()的情况。

方法:这次的栈用于处理()的情况,由于不涉及*,/,我们只用result来保存以往的结果,当遇到sign的时候,表示开始下一轮,把之前的sign和operator的结果加到result上。遇到“(”的时候,把上一轮的符号和结果压栈,接着按正常顺序处理括号中的值,等遇到")"之后,先从栈中弹出符号和当前结果相加后再放入result中。

class Solution {
public:
int calculate(string s) {
stack<int> stk;
int operand = 0;
int result = 0;
int sign = 1;
for(int i = 0; i < s.length(); i++) {
char ch = s[i];
if(isdigit(ch))
operand = 10*operand + (ch - '0');
else {
switch (ch) {
case '+':
result += sign*operand;
sign = 1;
operand = 0;break;
case '-':
result += sign*operand;
sign = -1;
operand = 0; break;
case '(':
stk.push(result);
stk.push(sign);
sign = 1;
result = 0;break;
case ')':
result += sign*operand;
result *= stk.top();
stk.pop();
result += stk.top();
stk.pop();
operand = 0;break;
}
}
}
return result + (sign * operand);
}
};

Calculator III

题目:LC772,在II的基础上有加入了*和/运算符。

方法:采用递归进行解决。当遇见'('的时候,我们继续从下一个字符开始进行解析,结果返回给n之后,再按照CalculatorI的方法进行计算。这里用了vector去模拟栈的用法,直接对vector.back()的元素进行处理。

这里还有一篇对整个计算器框架总结的比较好的文章

代码:

ass Solution {
public:
int calculate(string s) {
int i = 0;
return parseExpr(s, i);
}
int parseExpr(string& s, int& i) {
vector<int> nums;
char op = '+';
for (; i < s.length() && op != ')'; i++) {
if (s[i] == ' ') continue;
int n = s[i] == '(' ? parseExpr(s, ++i) : parseNum(s, i);
switch(op) {
case '+' : nums.push_back(n); break;
case '-' : nums.push_back(-n); break;
case '*' : nums.back() *= n; break;
case '/' : nums.back() /= n; break;
}
op = s[i];
}
int res = 0;
for (int n : nums) res += n;
return res;
}
int parseNum(string& s, int& i) {
int n = 0;
while(i < s.length() && isdigit(s[i]))
n = s[i++] - '0' + 10 * n;
return n;
}
};