NC21181. 重返小学
描述
时光依旧，岁月匆匆。转眼间，曾经的少年郭嘉烜已经长大成人，考上了一所优秀的大学——兰州大学。在经历了一年来自牛顿、莱布尼茨、拉普拉斯的精神洗礼后，他终于决定回到小学，重新回到加减乘除的怀抱中。
输入描述
第一行，一个整数T (1≤T≤100000)，表示案例的个数。
接下来的T行，每行一个字符串（长度小于等于100），字符串仅由0-9、+、-、*、/、^、!字符组成，数字表示一个数值，范围为[0,9]，且数字不存在前导零，其他符号表示一种运算规则，规则的描述如下：
+：数字1 +数字2 =两个数字之和，+号的优先级为1
-：数字1 -数字2 =两个数字之差，-号的优先级为1
*：数字1 *数字2 =两个数字之积，*号的优先级为2
/：数字1 /数字2 =两个数字之商（舍去小数），/号的优先级为2
^：数字1 ^数字2 =数字1的数字2次方，^号的优先级为3
!：数字1 ! =数字1的阶乘，!号的优先级为4
按照优先级从高到低的顺序依次计算，同级运算时，从左到右依次计算。
输入保证对于每个字符串，满足上述条件，一行输入，以换行符结束。保证式子的表达式语义正确。特别的，一切数值计算均受限于模65536的数域，即每一步运算都要对65536取模，取模的规则同C语言规范。同时，任意数的0次方等于1。
输出描述
T行，T个整数。
每行输出对应案例表达式运算的结果，如遇到除以0的算数错误，请输出ArithmeticException。
示例1
输入:
1 4*3/2^0+9
输出:
21
说明:
优先计算2!=2，之后以前一步的结果继续计算2!=2遇到换行符结束运算并输出示例2
输入:
2 2!! 3/2^4^4
输出:
2 ArithmeticException
说明:
优先计算2^4^4，由于其结果对65536取模为0，因此下一步运算变成3/0从而产生ArithmeticExceptionC++(clang++ 11.0.1) 解法, 执行用时: 507ms, 内存消耗: 1064K, 提交时间: 2023-07-27 21:08:03
#include<bits/stdc++.h>
using namespace std;
const int N=65536;
string s;
int f[N];
int flag;
int change(int l,int r)
{
int x=0;
for(int i=l;i<=r;i++)
x=x*10+(s[i]-'0');
return x;
}
int power(int x,int y)
{
if(y==0) return 1;
long long sum=1;
while(y)
{
if(y%2==1) sum=sum*x%N;
x=x*x%N;
y=y/2;
}
return sum;
}
long long deal(int l,int r)
{
int p1=-1,p2=-1,p3=-1,p4=-1,i;
for(i=l;i<=r;i++)
{
if(s[i]=='-'||s[i]=='+') p1=i;
if(s[i]=='*'||s[i]=='/') p2=i;
if(s[i]=='^') p3=i;
if(s[i]=='!') p4=i;
}
if(p1!=-1)
{
if(s[p1]=='+') return (deal(l,p1-1)+deal(p1+1,r))%N;
else return (deal(l,p1-1)-deal(p1+1,r))%N;
}
if(p2!=-1)
{
if(s[p2]=='*' ) return (deal(l,p2-1)*deal(p2+1,r))%N;
else
{
if(deal(p2+1,r)==0) flag=0;
else return (deal(l,p2-1)/deal(p2+1,r))%N;
}
}
if(p3!=-1)
{
return power(deal(l,p3-1),deal(p3+1,r));
}
if(p4!=-1)
{
return f[deal(l,p4-1)];
}
return change(l,r);
}
int main()
{
int t,i;
cin>>t;
f[0]=1;
for(i=1;i<N;i++)
f[i]=f[i-1]*i%N;
while(t--)
{
cin>>s;
flag=1;
int res=deal(0,s.size()-1);
if(flag==1)cout<<res<<endl;
else cout<<"ArithmeticException"<<endl;
}
return 0;
}