重返小学

就是表达式计算 这个没有括号 但是多了运算乘方和阶乘 这个思路其实会有一些不一样
因为不存在括号 所以我可以从表达式末尾开始遍历 根据运算优先级来进行运算
由高到低分别是

1. 加法减法
2. 乘法除法
3. 乘方
4. 阶乘

此处需要注意的点是除法 因为除数不能为0 所以进行除法时需要判断分母是否为除法
其余就很简单了 记得先预处理递归去做即可
代码如下

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int p = 65536;
int fac[200010];
string s;
int flag = 1;

ll qmi(ll a, ll b) {
  ll res = 1 % p;
  for (;b;b >>= 1) {
    if (b & 1) res = res * a % p;
    a = a * a % p;
  }
  return res;
}

ll stoi(int l, int r) {
  ll sum = 0;
  for (int i = l;i <= r; ++ i) {
    sum = sum * 10 + s[i] - '0';
  }
  return sum;
}

ll cal(int l, int r) {
  for (int i = r;i >= l; -- i) {
    if (s[i] == '+') return (cal(l, i - 1) % p + cal(i + 1, r) % p) % p;
    else if (s[i] == '-') return (cal(l, i - 1) % p - cal(i + 1, r) % p)  % p;
  }
  for (int i = r;i >= l; -- i) {
    if (s[i] == '*') return (cal(l, i - 1) % p * cal(i + 1, r) % p) % p;
    else if (s[i] == '/') {
      if (cal(i + 1, r) % p == 0) {
        flag = 0;
        return 65536;
      }
      else return (cal(l, i - 1) % p / cal(i + 1, r) % p) % p;
    }
  }
  for (int i = r;i >= l; -- i) {
    if (s[i] == '^') {
      //if (cal(i + 1, r) == 0) return 1;
      //cout << qmi(cal(l, i - 1) % p, cal(i + 1, r) % p) % p << '\n';
      return qmi(cal(l, i - 1) % p, cal(i + 1, r) % p) % p;
    }
  }
  for (int i = r;i >= l; -- i) {
    if (s[i] == '!') return fac[cal(l, i - 1)] % p;
  }
  return stoi(l, r) % p;
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  int t;cin >> t;
  fac[0] = 1, fac[1] = 1;
  for (int i = 2;i <= 200000; ++ i) fac[i] = fac[i - 1] * i % p;
  while (t --) {
    cin >> s;
    int a = cal(0, s.size() - 1);
    if (flag == 0) cout << "ArithmeticException\n";
    else cout << a << '\n';
    flag = 1;
    //注意要恢复现场 第一次WA在这
  }
}