这里说一种题解里面没有用过的**表达式树**写法（其实是语义树的某种水到天际的真子集写法）。
大概就是每个点要么是数值，要么是符号；对于一个符号$x$，我们通过计算其左右子树的值，并通过$x$的符号连接左右的值实现运算效果。对于一棵子树，它代表的就是原字符串的一个区间。同时，优先级也需要注意。假设对于某一棵子树内，既有`+`也有`*`也有`^`，那么根据优先级来，`*`的深度应该大于`+`的、`^`的深度应该大于`*`的，这样才能保证`+`是最后被计算到的。
然后本题只有`+`和`*`，并且需要$\bmod~10000$。
似乎表达式树的复杂度应该是$O(|S|)$的，但是原谅我写假了，在每一层会多算几遍，但是过$1e5$还是没问题的。
```cpp
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#define Mod 10000
#define rr register
#define MAXN 2000010
using namespace std ;
int tp, root ;
int N, brac[MAXN], stk[MAXN] ;
char In[MAXN], op[MAXN] ;
int L[MAXN], R[MAXN], ans, val[MAXN] ;
inline bool isop(const char &x){
return x == '+' || x == '-' || x == '*' || x == '/' || x == '^' ;
}
int build(const int &l, const int &r){
if (brac[l] == r) return build(l + 1, r - 1) ;
rr int rt = 0, ls = 0, rs = 0, x = 0 ;
for (rr int k = l ; k <= r ; ++ k){
if (In[k] == '(') k = brac[k] + 1 ; if (k > r) break ;
if ((In[k] == '+' || In[k] == '-') && k != l && !isop(In[k - 1])) { rt = k ; break ; }
if (In[k] == '*' || In[k] == '/') ls = k ; if (In[k] == '^' && !rs) rs = k ;
}
if (rt) x = rt ; else if (ls) x = ls ; else x = rs ;
if (!x) {
x = r, op[x] = '?' ;
sscanf(In + l, "%d", &val[x]) ;
val[x] %= Mod ; return x ;
}
op[x] = In[x] ; L[x] = build(l, x - 1), R[x] = build(x + 1, r) ; return x ;
}
int expow(int a, int b){
rr int res = 1 ;
while (b){
if (b & 1) (res *= a) %= Mod ;
(a *= a) %= Mod ; b >>= 1 ;
}
return res ;
}
int dp(const int &x){
if (op[x] == '?') return val[x] ;
rr int l = dp(L[x]) % Mod, r = dp(R[x]) % Mod, res = 0.0 ;
if (op[x] == '+') res = (l + r) % Mod ;
if (op[x] == '-') res = (l - r) % Mod ;
if (op[x] == '*') res = (l * r) % Mod ;
if (op[x] == '/') res = l * expow(r, Mod - 2) % Mod ;
if (op[x] == '^') res = expow(l ,r) ; return res ;
}
signed main(){
cin >> In + 1, N = strlen(In + 1) ;
for (rr int i = 1 ; i <= N ; ++ i){
if (In[i] == '(') stk[++ tp] = i ;
if (In[i] == ')') brac[i] = stk[tp], brac[stk[tp]] = i, tp -- ;
}
root = build(1, N), cout << dp(root) << endl ; return 0 ;
}
```