可能仅供tju食用哈哈哈
1.ac151-1（堆实现）
#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define For(i,j,k) for (int i=(j);i<=(k);i++)
#define rof(i,j,k) for (int i=(j);i>=(k);i--)
#define ull unsigned long long
#define lowbit(x) ((x)&(-(x)))
#define PII pair<int,int>
#define int long long
#define endl "\n"
#define ls rt<<1
#define rs rt<<1|1
typedef long long ll;
const int mod = 998244353;
const double eps = 1e-9;
const int N=2e6+7;
int n,m;
stack<int> numstack;
stack<char> optstack;
string s;//本身字符串
string le;//要往左多加的字符串
int len;
void match(){
//处理括号匹配
s="("+s+")";
len=s.length();
//补充左括号和右括号来得到正确的表达式
for(int i=0;i<len;i++){
if(s[i]==')'){
le+="(";
}else if(s[i]=='('){
s=s+")";
}
}
s=le+s;
}
void cal(){
int a=numstack.top();//这里写两个，因为这个是两个数在算
numstack.pop();
int b=numstack.top();
numstack.pop();
int c=optstack.top();//把符号弄出来
optstack.pop();
int d;
if(c=='+') d=b+a;
else if(c=='-') d=b-a;
else if(c=='*') d=b*a;
else if(c=='/') d=b/a;
else{
d=pow(b,a);
}
numstack.push(d);
}
void solve(){
cin>>s;
match();
len=s.length();
//接下来开始正确遍历字符串
for(int i=0;i<=len;i++){
//如果是数字的话
if(s[i]>='0'&&s[i]<='9'){
int j=i,x=0;
while(s[j]>='0'&&s[j]<='9'){//将数字连续存入，因为不一定是个位数
x=x*10;
x+=s[j]-'0';
j++;
}
i=j-1;
numstack.push(x);
}else{
if(s[i]=='+'||s[i]=='-'){
//这里我们一定一定要特判一下负数的情况，到底是减法还是负数
if(s[i]=='-'&&!(s[i-1]>='0'&&s[i-1]<='9'||s[i-1]==')')){
if(!s[i+1]=='('){
int j=i+1;
int x=0;
while(s[j]>='0'&&s[j]<='9'){
x*=10;
x+=s[j]-'0';
j++;
}
i=j-1;
numstack.push(-x);
}else{
numstack.push(-1);
optstack.push('*');
}
}else{//这里是减法
while(optstack.top()!='(') cal();
optstack.push(s[i]);
}
}else if(s[i]=='*'||s[i]=='/'){//接下来这几个就正常每次放入前看能不能计算即可
while(optstack.top()=='*'||optstack.top()=='/'||optstack.top()=='^') cal();
optstack.push(s[i]);
}else if(s[i]=='^'){
while(optstack.top()=='^') cal();
optstack.push(s[i]);
}else if(s[i]==')'){
while(optstack.top()!='(') cal();
optstack.pop();
}else if(s[i]=='('){
optstack.push(s[i]);
}
}
}
//输出元素即栈顶元素即可
cout<<numstack.top()<<endl;
}
signed main(){
int t=1;
//cin>>t;
while(t--){
solve();
}
}
2.ac151-2（递归实现）
#include<bits/stdc++.h>
using namespace std;
string s;
string ss;
int number(int le, int ri){
//处理字符串n中[le,ri]的数字
int res = 0;
for(int i = le; i <= ri; i++){
res=res*10;
res+=s[i]-'0';
}
return res;
}
int cal(int l, int r){
int cnt = 0, add = 0, mul = 0, power = 0;
for(int i = l; i <= r; i++){
if(s[i] == '('){
cnt++;
}else if(s[i] == ')'){
cnt--;
}else if(!cnt){ //这里我们记录括号外的最后一个符号位置，优先级不同的分开记录
if(s[i]=='+'||s[i]=='-') add=i;
else if(s[i]=='*'||s[i]=='/') mul=i;
else if(s[i]=='^') power=i;
}
}
if(cnt > 0 && s[l] == '(')//记得要去掉多余的括号
return cal(l + 1, r);
else if(cnt < 0 && s[r] == ')')
return cal(l, r - 1);
else if(cnt==0&&add==0&&mul==0&&power==0){
//如果剩下的式子包在括号里或者只剩下数字，则得到这个数字
if(s[l] == '(' && s[r] == ')'){
return cal(l + 1, r - 1);
}
return number(l, r);
}
if(add!=0){
//这里要注意分开看
if(s[add] == '+'){//加号我们正常处理
return cal(l, add-1) + cal(add+1, r);
}
else{//但对于减号我们要分清楚到底是负数还是减法这个差的很多
if(s[add-1]=='*'){//如果-前面是*那么一定是负号
return cal(l, add-2)*(-1)*cal(add+1, r);
}else if(s[add-1]=='/'){//如果-前面是/那么一定是负号
return cal(l, add-2)/((-1)*cal(add+1, r));
}else{//其他的正常处理
return cal(l, add-1) - cal(add+1, r);
}
}
}
//接下来的符号正常处理即可
if(mul!=0){
if(s[mul] == '*') return cal(l, mul-1) * cal(mul+1, r);
else return cal(l, mul-1) / cal(mul+1, r);
}
if(power!=0) return pow(cal(l, power-1), cal(power+1, r));
}
int main(){
cin>>s;
//这里为了处理开头负号所以加上个左右括号
s='('+s+')';
//递归处理字符串即可
cout<<cal(0,s.length()-1)<<endl;
return 0;
}
3.lg8085
#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define For(i,j,k) for (int i=(j);i<=(k);i++)
#define rof(i,j,k) for (int i=(j);i>=(k);i--)
#define ull unsigned long long
#define lowbit(x) ((x)&(-(x)))
#define PII pair<int,int>
#define int long long
#define endl "\n"
#define ls rt<<1
#define rs rt<<1|1
typedef long long ll;
const int inf = 1e18;
const double eps = 1e-9;
const int N=2e6+7;
int n,m;
int a[N];//修改明文后的数组
int b[N];//修改密文后的数组
int ne[N];//b[i]数组的next数组
string p[N];//密文字符串组
int pi[N];//密文为字符串的next数组
map<string,int> mp;//标记是否出现过
void getnext(){
//接下来找b[i]数组的next数组
ne[1]=0;
for(int i=2,j=0;i<=m;i++){
while(j&&b[i]!=b[j+1]) j=ne[j];
if(b[i]==b[j+1]) j++;
ne[i]=j;
}
//接下来找字符串数组的next数组
pi[1]=0;
for(int i=2,j=0;i<=m;i++){
while(j&&p[i]!=p[j+1]) j=pi[j];
if(p[i]==p[j+1]) j++;
pi[i]=j;
}
}
int kmp(){
//正常求KMP
for(int i=1,j=0;i<=n;i++){
while(j&&a[i]!=b[j+1]){
//当a[i]上一次出现的地方大于b现在的长度时说明也等于没有出现过
if(a[i]>=j+1&&b[j+1]>=inf) break;
j=max(ne[j],pi[j]);
//这里跳的时候少跳一点，尽量往最优的地方跳，这也是维护两个next数组的原因
}
if(a[i]==b[j+1]||(a[i]>=j+1&&b[j+1]==inf)) j++;
if(j==m) return i-m+1;
}
return -1;
}
void solve(){
string s;
//维护并存入a[i]数组
n=1;
while(cin>>s&&s!="$"){
if(!mp[s]){//没有出现过记为inf
mp[s]=n;
a[n]=inf;
}else{
a[n]=n-mp[s];//出现过标记上一个出现的位置
mp[s]=n;
}
n++;
}
mp.clear();
n--;
//维护并存入b[i]数组
m=1;
while(cin>>s&&s!="$"){
p[m]=s;
if(!mp[s]){
mp[s]=m;
b[m]=inf;
}else{
b[m]=m-mp[s];
mp[s]=m;
}
m++;
}
m--;
getnext();//求next数组
cout<<kmp()<<endl;//得出答案即可
}
signed main(){
int t=1;
while(t--){
solve();
}
}
