一、基本計(jì)算器Ⅰ
題目鏈接
題目描述：
給你一個(gè)字符串表達(dá)式 s ，請(qǐng)你實(shí)現(xiàn)一個(gè)基本計(jì)算器來計(jì)算并返回它的值。
注意:不允許使用任何將字符串作為數(shù)學(xué)表達(dá)式計(jì)算的內(nèi)置函數(shù)，比如 eval() 。
示例 1：
輸入：s = “1 + 1”
輸出：2
示例 2：
輸入：s = " 2-1 + 2 "
輸出：3
示例 3：
輸入：s = “(1+(4+5+2)-3)+(6+8)”
輸出：23
提示：
1 <= s.length <= 3 * 105
s 由數(shù)字、‘+’、‘-’、‘(’、‘)’、和 ’ ’ 組成
s 表示一個(gè)有效的表達(dá)式
‘+’ 不能用作一元運(yùn)算(例如， “+1” 和 “+(2 + 3)” 無效)
‘-’ 可以用作一元運(yùn)算(即 “-1” 和 “-(2 + 3)” 是有效的)
輸入中不存在兩個(gè)連續(xù)的操作符
每個(gè)數(shù)字和運(yùn)行的計(jì)算將適合于一個(gè)有符號(hào)的 32位 整數(shù)
思路分析
用兩個(gè)棧：nums：存數(shù)字字符ops：存符號(hào)字符
從前向后遍歷字符串，因?yàn)檫@道題只有+/-，所以不用考慮符號(hào)優(yōu)先級(jí)問題。
遍歷過程有以下幾種情況：
1?? 空格：直接跳過
2?? 數(shù)字字符：向后遍歷取出完整數(shù)字，放入nums中。
3??(：直接放入ops中，等待)與之匹配
4??)：利用兩個(gè)棧計(jì)算，直到遇到(，結(jié)果放入nums中，再把(出棧
5??+/-：先把前面能計(jì)算的都計(jì)算了（一直算到遇到(為止），結(jié)果放入nums中，符號(hào)放入ops中
關(guān)于首字符帶符號(hào)的處理：
可以先往nums中加一個(gè)0元素，這樣-就可以算進(jìn)去。
關(guān)于(+和(-的處理：
每次遇到+/-的時(shí)候判斷前一個(gè)字符是否是(，如果是就往nums中添加0。
關(guān)于空格的處理：
這里不能遇到空格后跳過，因?yàn)榭赡艹霈F(xiàn)"1-( -2)"這種情況，所以先預(yù)處理字符串把空格全部消掉。
代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-498620.html
class Solution {
public:
stack<int> nums;
stack<char> ops;
unordered_map<char, function<int(int, int)>> hash = {
{'+', [](int x, int y){return x + y;}},
{'-', [](int x, int y){return x - y;}},
};
void delBlack(string& s)
{
auto it = s.find(" ");
while(it != -1)
{
s.replace(it, 1, "");
it = s.find(" ");
}
}
void calc()
{
if(nums.size() < 2 || ops.empty()) return;
int right = nums.top();
nums.pop();
int left = nums.top();
nums.pop();
char op = ops.top();
ops.pop();
nums.push(hash[op](left, right));
}
int calculate(string s) {
// 去掉空格
delBlack(s);
// 防止首元素為-
nums.push(0);
int n = s.size();
for(int i = 0; i < n; i++)
{
if(isdigit(s[i]))// 數(shù)字字符
{
int cur = 0, j = i;
while(j < n && isdigit(s[j]))
{
cur = cur * 10 + (s[j++] - '0');
}
nums.push(cur);
i = j - 1;
}
else// 符號(hào)字符
{
if(s[i] == '(') ops.push(s[i]);
else if(hash.count(s[i]))// + -
{
// "(+"情況
if (i > 0 && (s[i - 1] == '('))
{
nums.push(0);
}
// 入棧前先把前面的計(jì)算了
while(ops.size() && ops.top() != '(')
{
calc();
}
ops.push(s[i]);
}
else// ')'
{
// 一直算到 '('
while(ops.size() && ops.top() != '(')
{
calc();
}
ops.pop();
}
}
}
while(!ops.empty())
calc();
return nums.top();
}
};
二、基本計(jì)算器Ⅱ
題目鏈接
題目描述：
給你一個(gè)字符串表達(dá)式 s ，請(qǐng)你實(shí)現(xiàn)一個(gè)基本計(jì)算器來計(jì)算并返回它的值。
整數(shù)除法僅保留整數(shù)部分。
你可以假設(shè)給定的表達(dá)式總是有效的。所有中間結(jié)果將在 [-231, 231 - 1] 的范圍內(nèi)。
注意：不允許使用任何將字符串作為數(shù)學(xué)表達(dá)式計(jì)算的內(nèi)置函數(shù)，比如 eval() 。
示例 1：
輸入：s = “3+2*2”
輸出：7
示例 2：
輸入：s = " 3/2 "
輸出：1
示例 3：
輸入：s = " 3+5 / 2 "
輸出：5
提示：
1 <= s.length <= 3 * 105
s 由整數(shù)和算符 (‘+’, ‘-’, ‘*’, ‘/’) 組成，中間由一些空格隔開
s 表示一個(gè) 有效表達(dá)式
表達(dá)式中的所有整數(shù)都是非負(fù)整數(shù)，且在范圍 [0, 231 - 1] 內(nèi)
題目數(shù)據(jù)保證答案是一個(gè) 32-bit 整數(shù)
思路分析：
這道題跟上面一道題多了一個(gè)符號(hào)優(yōu)先級(jí)問題，為了解決這個(gè)問題，可以加入一個(gè)符號(hào)優(yōu)先級(jí)表：
unordered_map<char,int> oper_pri = {
{'+',1},
{'-',1},
{'*',2},
{'/',2},
};
當(dāng)遇到符號(hào)+ - * /的時(shí)候先判斷優(yōu)先級(jí)：oper_pri[ops.top()] >= oper_pri[s[i]]的時(shí)候說明可以計(jì)算前面的表達(dá)式了，先計(jì)算前面的，然后再把符號(hào)添加進(jìn)ops中。
那遇到)也要計(jì)算前面的，需不需要判斷優(yōu)先級(jí)呢？
不需要，因?yàn)樵?code>()內(nèi)部已經(jīng)自動(dòng)處理完了。文章來源：http://www.zghlxwxcb.cn/news/detail-498620.html
代碼如下：
class Solution {
public:
stack<int> nums;
stack<char> ops;
unordered_map<char, function<int(int, int)>> hash = {
{'+', [](int x, int y){return x + y;}},
{'-', [](int x, int y){return x - y;}},
{'*', [](int x, int y){return x * y;}},
{'/', [](int x, int y){return x / y;}},
};
unordered_map<char,int> oper_pri = {
{'+',1},
{'-',1},
{'*',2},
{'/',2},
};
void delBlack(string& s)
{
auto it = s.find(" ");
while(it != -1)
{
s.replace(it, 1, "");
it = s.find(" ");
}
}
void calc()
{
if(nums.size() < 2 || ops.empty()) return;
int right = nums.top();
nums.pop();
int left = nums.top();
nums.pop();
char op = ops.top();
ops.pop();
nums.push(hash[op](left, right));
}
int calculate(string s) {
// 去掉空格
delBlack(s);
// 防止首元素為-
nums.push(0);
int n = s.size();
for(int i = 0; i < n; i++)
{
if(isdigit(s[i]))// 數(shù)字字符
{
int cur = 0, j = i;
while(j < n && isdigit(s[j]))
{
cur = cur * 10 + (s[j++] - '0');
}
nums.push(cur);
i = j - 1;
}
else// 符號(hào)字符
{
if(s[i] == '(') ops.push(s[i]);
else if(hash.count(s[i]))// + - * /
{
// "(+"情況
if (i > 0 && (s[i - 1] == '('))
{
nums.push(0);
}
// 入棧前先把前面的計(jì)算了
while(ops.size() && ops.top() != '(' && oper_pri[ops.top()] >= oper_pri[s[i]])
{
calc();
}
ops.push(s[i]);
}
else// ')'
{
// 一直算到 '('
while(ops.size() && ops.top() != '(')
{
calc();
}
ops.pop();
}
}
}
while(!ops.empty())
calc();
return nums.top();
}
};
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】雙棧法解決表達(dá)式計(jì)算問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
