問題描述
給你一個字符串表達(dá)式 s ，請你實現(xiàn)一個基本計算器來計算并返回它的值。
整數(shù)除法僅保留整數(shù)部分。
示例 1：
輸入：s = "3+2*2"
輸出：7
示例 2：
輸入：s = " 3/2 "
輸出：1
提示：
1 <= s.length <= 3 * 105-
s由整數(shù)和算符('+', '-', '*', '/')組成，中間由一些空格隔開 -
s表示一個 有效表達(dá)式 - 表達(dá)式中的所有整數(shù)都是非負(fù)整數(shù)，且在范圍
[0, 231 - 1]內(nèi) - 題目數(shù)據(jù)保證答案是一個 32-bit 整數(shù)
棧思想
想象一下，一個計算器怎么實現(xiàn)，一般來說都是使用棧這個數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)的。那么如何確定不同符號的優(yōu)先級呢？
首先，'*'與'/'的優(yōu)先級要高于'+'和'-'。那么我們制定一個策略：
- 當(dāng)遇到
'*'與'/'的時候，我們不將當(dāng)前這個數(shù)字進(jìn)行入棧操作，而是將這個數(shù)字與棧頂元素進(jìn)行 符號運算，將運算結(jié)果更新為當(dāng)前棧頂元素。 - 當(dāng)遇到
'+'和'-'時，我們直接將當(dāng)前元素入棧，只不過特別的，對于'-'，我們?nèi)霔５氖钱?dāng)前數(shù)字的相反數(shù)。
例如，對于下面的表達(dá)式
初始化符號presign = '+'，我們遍歷到一個非數(shù)字符號的時候，我們將前面的數(shù)字入棧，前面的數(shù)字也就是數(shù)字3，然后我們可以將3直接入棧
第一步
往后繼續(xù)，遇到符號 '*'，我們將前面的數(shù)字2入棧，更新當(dāng)前的presign為'*'
第二步
到字符串最后一位也是一個結(jié)束的標(biāo)志，我們需要將前面的數(shù)字進(jìn)行入棧，但是當(dāng)前的presign為'*'，我們將當(dāng)前數(shù)字2與棧頂數(shù)字2進(jìn)行相乘為4，然后更新為棧頂元素。
第三步
最后，將棧內(nèi)所有的元素相加就能夠得到最終的計算結(jié)果：
C++實現(xiàn)（vector模擬棧）
class Solution {
public:
int calculate(string s) {
int n = s.length();
vector<int> nums; // 聲明一個向量容器模擬棧
// 初始化前一個數(shù)的符號為+號
char presign = '+';
int num = 0;
for(int i = 0;i < n;++i){
if(isdigit(s[i])) {
// 假如是數(shù)字
num = num * 10 + (s[i] - '0');
}
if(!isdigit(s[i]) && s[i] != ' ' || i == n-1) {
// 不是數(shù)字也不是符號，即是一個運算符或者到達(dá)了字符串的結(jié)尾
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; // 求和得出結(jié)果
for(auto each:nums) ret += each;
return ret;
}
};
Go實現(xiàn)（slice模擬棧）
func calculate(s string) int {
n := len(s)
nums := []int{}
// 初始化
num := 0
var presign byte = '+'
for i := 0; i < n; i++ {
// 判斷當(dāng)前字符是否為數(shù)字
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
}
// 更新符號與數(shù)值
presign = s[i]
num = 0
}
}
ret := 0
for _, val := range nums {
ret += val
}
return ret
}
注意：
這個計算器還是比較簡單的，只包括('+', '-', '*', '/')這四種運算符，還不包括括號運算符，并且數(shù)字都是非負(fù)整數(shù)。
參考：
