【栈与队列】基本计算器 II
【栈与队列】基本计算器 II
227. 基本计算器 II
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
**注意：**不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1：
输入：s = "3+2*2"
输出：7示例 2：
输入：s = " 3/2 "
输出：1示例 3：
输入：s = " 3+5 / 2 "
输出：5提示：
1 <= s.length <= 3 * 105s由整数和算符('+', '-', '*', '/')组成，中间由一些空格隔开s表示一个 有效表达式- 表达式中的所有整数都是非负整数，且在范围
[0, 231 - 1]内 - 题目数据保证答案是一个 32-bit 整数
解题思路：栈思想模拟
这类题型其实都属于【表达式求值】，都是可以利用栈来模拟解决的，一般可以给出一个栈来存放数字，一个栈来存放操作符，然后根据题目给出的表达式类型是前缀表达式、中缀表达式还是后缀表达式来分别解决，甚至我们可以将中缀表达式转化为后缀表达式来解决，会更加简单！
不过这里因为这个系列是比较基础的，所以不会涉及到太深太难的知识，后面会出专门的关于【表达式求值】的专题来学习！
因为这道题其实就是一个分情况讨论的问题，根据字符串类型的不同，来进行不同的情况处理！如下所示：
其实这道题我们用一个 op 来代替操作符即可，而不需要专门搞一个栈来存放这些操作符，因为 op 是 + 号的话，则对它两边的数直接入栈，而如果 op 是 - 号的话，我们是将当前数字变为负数然后入栈，这样子方便我们后面对栈中元素的集体相加。
而对于 * 号和 / 号来说，则需要将栈顶元素先拿出来与当前数字进行运算，因为它们的优先级在该表达式中是最高的，进行运算完再将结果入栈！
等到最后遍历字符串完毕之后，栈中的元素就是所有的结果，将它们累加起来即可！
还要注意的是，因为题目给的是字符串表达式，有可能数字是多位数，所以我们需要获取一个完整的数字，这里单独封装一个 get_whole_num() 接口来实现！
另外就是初始化操作符的问题，op 应该初始化为 +，而不能是 - 或者 * 或者 / 或者是其它的，因为我们循环进去之后判断的是这四个操作符，并且如果是 * 或者 / 的话，会出现优先级问题而调用 st.top() 而导致错误，因为一开始栈顶并没有元素！
class Solution {
public:
int calculate(string s) {
stack<int> st;
char op = '+'; // 细节，初始化为+号
int i = 0;
while(i < s.size())
{
if('0' <= s[i] && s[i] <= '9')
{
// 获取一个完整的数字
int num = get_whole_num(s, i); // 注意这里的i传入之后位置是可能会向后移动的
// 判断当前的操作符：
if(op == '+')
st.push(num);
else if(op == '-')
st.push(-num); // 注意负号的话我们入栈的是一个负数
else if(op == '*')
st.top() *= num;
else
st.top() /= num;
}
else if(s[i] == ' ') // 空格直接跳过
i++;
else
op = s[i++];
}
// 最后将栈中元素都相加然后返回
int sum = 0;
while(!st.empty())
{
sum += st.top();
st.pop();
}
return sum;
}
int get_whole_num(string& s, int& i)
{
int tmp = 0;
while('0' <= s[i] && s[i] <= '9')
{
tmp = tmp*10 + (s[i] - '0');
i++;
}
return tmp;
}
};腾讯云开发者
