重返小学

这个题比表达式求值既高级又低级.高级在需要算阶乘,低级在没有括号问题

在求阶乘的时候,如果我们直接自己写函数,那么就会诱发超时或者超空间.因此有位大佬运用预处理的方式成功AC了,向她致敬

#include<iostream>
#include<cmath>
using namespace std;
const int N=65536;
int f[N];//存储阶乘结果
string a;
bool flag;
int power(int x, int y)//递归式快速幂
{
    int temp;
    if(y == 0)
        return 1;
    temp = power(x, (y/2));
    if (y%2 == 0)
        return (temp*temp)%N;
    else
    {
        if(y>0)
            return (x*temp*temp)%N;
        else
            return ((temp*temp)/x)%N;
    }
}
int power2(int x,int y)//非递归式快速幂
{
	if(y==0)return 1;
    long long sum=1;//防止爆数据
    while(y)
    {
    	if(y&1)
        {
        	sum=sum*x%N;
        }
        x=x*x%N;
        y=y>>1;
        
    }
    return sum;
}
int zhuan(int l,int r)
{
	int sum=0;
    for(int i=l;i<=r;i++)
    	sum=sum*10+a[i]-'0';
	return sum;
}
int cal(int l,int r)
{
	int pos1=-1,pos2=-1,pos3=-1,pos4=-1;
    for(int i=l;i<=r;i++)
    {
    	if(a[i]=='+'||a[i]=='-') pos1=i;
        if(a[i]=='*'||a[i]=='/') pos2=i;
        if(a[i]=='^') pos3=i;
        if(a[i]=='!')pos4=i;
    }
    if(pos1==-1&&pos2==-1&&pos3==-1&&pos4==-1)
    	return zhuan(l,r);
    else if(pos1!=-1)
    {
    	if(a[pos1]=='+')return (cal(l,pos1-1)+cal(pos1+1,r))%N;
        else return (cal(l,pos1-1)-cal(pos1+1,r))%N;
    }
    else if(pos2!=-1)
    {
    	if(a[pos2]=='*')return (cal(l,pos2-1)*cal(pos2+1,r))%N;
        else 
        {
        	if(cal(pos2+1,r)==0)
        		flag=1;
        	else return (cal(l,pos2-1)/cal(pos2+1,r))%N;
        }
    }
    else if(pos3!=-1)
    {
    	return power(cal(l,pos3-1),cal(pos3+1,r));
    }
    else if(pos4!=-1)
    {
    	int a=cal(l,pos4-1);
        return f[a];
    }
    return 0;
}
int main()
{
	int T;
    cin>>T;
    f[0]=1;
    for(int i=1;i<N;i++)
    	f[i]=f[i-1]*i%N;
    while(T--)
    {
    	cin>>a;
        flag=0;
        int res=cal(0,a.size()-1);
        if(!flag)cout<<res<<endl;
        else cout<<"ArithmeticException"<<endl;
    }
    return 0;
}