爽了（密码门题解）
2024-05-12 19:56:36
发布于：广东
22阅读
0回复
0点赞
题目（信奥团队里的）
这个代码主要是娱乐向owo
温馨提示：结果自动对998244353取模，数据太大用可能会对减法和除法影响
#include <iostream>
#include <cstdio>
#include <stack>
#include <queue>
#define int long long
using namespace std;
const int mod = 998244353;
stack <int> s;
queue <int> q;
string a;
bool check(char a){//检查运算优先级是否高于栈顶
if(s.empty()) return 1;
if(s.top() == -1e12-6) return 1;
if(a == '+' || a == '-') return 0;
if(a == '*' || a == '/') return -1 >= s.top() && s.top() >= -1e12-2;
else return -1 >= s.top() && s.top() >= -1e12-4;
}int turn_(char a){//转换成可读的数字，避免数字符号搞混
if(a == '+') return -1e12-1;
if(a == '-') return -1e12-2;
if(a == '*') return -1e12-3;
if(a == '/') return -1e12-4;
if(a == '^') return -1e12-5;
if(a == '(') return -1e12-6;
return -1e12-7;
}char re_turn(int n){//测试，无实际用处
if(n >= 0) return n + '0';
if(n == -1e12-1) return '+';
if(n == -1e12-2) return '-';
if(n == -1e12-3) return '*';
if(n == -1e12-4) return '/';
if(n == -1e12-5) return '^';
if(n == -1e12-6) return '(';
return ')';
}int pow(int n, int k){//乘方
n %= mod;
int tmp = 1;
while(k){
if(k % 2) tmp = tmp * n % mod;
n = n * n % mod, k /= 2;
}return tmp;
}
void _init(string a){//转后缀表达式
for(int i = 0; a[i] != '\0'; i++){
if(isdigit(a[i])){//如果是数字
if(i && isdigit(a[i - 1])) q.back() = (q.back() * 10 + a[i] - '0') % mod;//多位数
else q.push(a[i] - '0');//单位数直接进队列
}
else if(a[i] == ')'){//右括号
while(s.top() != -1e12-6){//不是左括号就一直进队列
q.push(s.top());
s.pop();
}s.pop();
}else if(s.empty() || a[i] == '(' || s.top() == -1e12-6) s.push(turn_(a[i]));//如果前面没有运算就直接进栈
else if(check(a[i])) s.push(turn_(a[i]));
else{
while(!check(a[i])){//一直比较运算优先级
q.push(s.top());
s.pop();
}s.push(turn_(a[i]));
}
}
while(!s.empty()){//把剩余的放入队列
q.push(s.top());
s.pop();
}
}int calc(){//计算
while(!q.empty()){
if(q.front() >= 0) s.push(q.front());
else{
int m = s.top();
s.pop();
int n = s.top();
s.pop();
if(q.front() == -1e12-1) s.push((n + m) % mod);
else if(q.front() == -1e12-2) s.push((n - m) % mod);
else if(q.front() == -1e12-3) s.push((n * m) % mod);
else if(q.front() == -1e12-4) s.push((n / m) % mod);
else s.push(pow(n, m));
}
q.pop();
}return s.top();
}
signed main(){
cin >> a;
_init(a);
cout << calc();
return 0;
}
有帮助，赞一个