题解 P1981 【表达式求值 】

#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 ;
}

2019-07-22 15:00:48 in 题解