基本計算器㈠（只有加減、括號）
鏈接: link.
基本計算器㈡（只有加減、乘除）
鏈接: link.
基本計算器㈢（加減乘除模等、括號）
完全運算式，雙堆疊解法nums+ops
定義兩個堆疊：
nums：存放所有數字
ops：存放所有數字以外的操作
思路： 從前往后遍歷當
- 遇到空格：pass
- 遇到 ’ ( '：加入ops中等待匹配
- 遇到 ’ ) '：使用現有nums和
- 遇到數字：從當前位置開始遍歷，取出數字整體，加入nums
- “+ - * / ^ %”：將符號放入ops，在放入之前先把堆疊內可以算的都算掉（只有「堆疊內運算子」比「當前運算子」優先級高/同等，才進行運算），使用現有nums和ops計算，直到沒有操作或者遇到左括號，計算結果放到nums
舉個🌰：
當我們讀到字串 1+2時，當前堆疊操作為+
- 如果
1+2后面接-1或+1，滿足上面黃色注釋，因此我們把1+2算出來，并把結果存入nums堆疊中 - 如果
1+2后面接*2或/2，不滿足上面黃色注釋，此時我們就不能把1+2算出來
細節：
- 第一個數可能為負數，為減少判斷，直接nums中先存個0
- 題目可能很考驗細節，給你的字串可能有 空格、（+1）、（-1）等，為此我們需要預處理一下字串，減少踩坑幾率
- nums堆疊可能資料大于int，當題目卡資料時，可以改成long型別試試
完整代碼
#include<bits/stdc++.h>
using namespace std;
//預處理函式
//替換空格、負數，（-2）->（0-2），（+4）->(0+4)
string replace(string& base, string src, string dst) {
int pos = 0, srclen = src.size(), dstlen = dst.size();
while ((pos = base.find(src, pos)) != string::npos) {
base.replace(pos, srclen, dst);
pos += dstlen;
}
return base;
}
//計算函式
void calc(stack<int> &nums, stack<char> &ops) {
if (nums.empty() || nums.size() < 2)
return;
if (ops.empty())
return;
int b = nums.top();
nums.pop();
int a = nums.top();
nums.pop();
char op = ops.top();
ops.pop();
int ans = 0;
if (op == '+') ans = a + b;
else if (op == '-') ans = a - b;
else if (op == '*') ans = a * b;
else if (op == '/') ans = a / b;
else if (op == '^') ans = (int)pow(a, b);
else if (op == '%') ans = a % b;
nums.push(ans);
}
int main() {
map<char,int> m;
//map存盤符號優先級
m.insert(make_pair('+',1));
m.insert(make_pair('-',1));
m.insert(make_pair('*',2));
m.insert(make_pair('/',2));
m.insert(make_pair('%',3));
m.insert(make_pair('^',3));
//雙堆疊
stack<char> ops;
stack<int> nums;
string s;
getline(cin,s);
//取出閑雜符號
s=replace(s," ","");
s=replace(s,"(-","(0-");
s=replace(s,"(+","(0+)");
int len=s.size();
nums.push(0);//防止第一個字符為符號
for(int i=0; i<len; i++) {
char c=s[i];
if(c=='(') {
ops.push(c);
} else if(c==')') {
while(!ops.empty()) {
if(ops.top()!='(') {
calc(nums,ops);
} else {
ops.pop();
break;
}
}
} else {
if(c>='0'&&c<='9') {
int u=0;
int j=i;
//整體取出數字
while(j<len&&s[j]>='0'&&s[j]<='9') {
u=u*10+(s[j++]-'0');
}
nums.push(u);
i=j-1;
} else {
while(!ops.empty()&&ops.top()!='(') {
char prev=ops.top();
if(m.find(prev)->second>=m.find(c)->second) {
calc(nums,ops);
} else {
break;
}
}
ops.push(c);
}
}
}
while(!ops.empty()) {
calc(nums,ops);
}
cout<<nums.top();
}
以后絕對不能栽在計算器上了，
思路來自LeetCode【宮水三葉】，三葉yyds，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/275544.html
標籤：其他
上一篇：C++陣列中元素組合出最大值