刷题日记--完全计算器（计算器通解）
基本计算器㈠（只有加减、括号）
链接: .
基本计算器㈡（只有加减、乘除）
链接: .
基本计算器㈢（加减乘除模等、括号）
完全表达式，双栈解法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。