问题描述
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
示例 1：
输入：s = "3+2*2"
输出：7
示例 2：
输入：s = " 3/2 "
输出：1
提示：
1 <= s.length <= 3 * 105-
s由整数和算符('+', '-', '*', '/')组成，中间由一些空格隔开 -
s表示一个 有效表达式 - 表达式中的所有整数都是非负整数，且在范围
[0, 231 - 1]内 - 题目数据保证答案是一个 32-bit 整数
栈思想
想象一下，一个计算器怎么实现，一般来说都是使用栈这个数据结构来实现的。那么如何确定不同符号的优先级呢？
首先，'*'与'/'的优先级要高于'+'和'-'。那么我们制定一个策略：
- 当遇到
'*'与'/'的时候，我们不将当前这个数字进行入栈操作，而是将这个数字与栈顶元素进行 符号运算，将运算结果更新为当前栈顶元素。 - 当遇到
'+'和'-'时，我们直接将当前元素入栈，只不过特别的，对于'-'，我们入栈的是当前数字的相反数。
例如，对于下面的表达式
初始化符号presign = '+'，我们遍历到一个非数字符号的时候，我们将前面的数字入栈，前面的数字也就是数字3，然后我们可以将3直接入栈
第一步
往后继续，遇到符号 '*'，我们将前面的数字2入栈，更新当前的presign为'*'
第二步
到字符串最后一位也是一个结束的标志，我们需要将前面的数字进行入栈，但是当前的presign为'*'，我们将当前数字2与栈顶数字2进行相乘为4，然后更新为栈顶元素。
第三步
最后，将栈内所有的元素相加就能够得到最终的计算结果：
C++实现（vector模拟栈）
class Solution {
public:
int calculate(string s) {
int n = s.length();
vector<int> nums; // 声明一个向量容器模拟栈
// 初始化前一个数的符号为+号
char presign = '+';
int num = 0;
for(int i = 0;i < n;++i){
if(isdigit(s[i])) {
// 假如是数字
num = num * 10 + (s[i] - '0');
}
if(!isdigit(s[i]) && s[i] != ' ' || i == n-1) {
// 不是数字也不是符号，即是一个运算符或者到达了字符串的结尾
switch(presign){
case '+':{
nums.push_back(num);break;
}
case '-':{
nums.push_back(-num);break;
}
case '*':{
nums.back() = nums.back() * num;break;
}
case '/':{
nums.back() = nums.back() / num;break;
}
default:break;
}
presign = s[i];
num = 0;
}
}
int ret = 0; // 求和得出结果
for(auto each:nums) ret += each;
return ret;
}
};
Go实现（slice模拟栈）
func calculate(s string) int {
n := len(s)
nums := []int{}
// 初始化
num := 0
var presign byte = '+'
for i := 0; i < n; i++ {
// 判断当前字符是否为数字
isdigit := (s[i] >= '0' && s[i] <= '9')
if isdigit {
num = num * 10 + int(s[i] - '0')
}
if !isdigit && s[i] != ' ' || i == n - 1 {
switch presign {// 各种不同符号的处理方法
case '+':
nums = append(nums,num)
case '-':
nums = append(nums,-num)
case '*':
nums[len(nums)-1] *= num
case '/':
nums[len(nums)-1] /= num
}
// 更新符号与数值
presign = s[i]
num = 0
}
}
ret := 0
for _, val := range nums {
ret += val
}
return ret
}
注意：
这个计算器还是比较简单的，只包括('+', '-', '*', '/')这四种运算符，还不包括括号运算符，并且数字都是非负整数。
参考：
