_皎月半洒花 的博客

_皎月半洒花 的博客

反抗命运的镇魂曲停歇之前,你绝对不可以说我懦弱,绝对不可以说我没有殊死一搏。

题解 P1981 【表达式求值 】

posted on 2019-07-22 15:00:48 | under 题解 |

这里说一种题解里面没有用过的表达式树写法(其实是语义树的某种水到天际的真子集写法)。

大概就是每个点要么是数值,要么是符号;对于一个符号 $x$ ,我们通过计算其左右子树的值,并通过 $x$ 的符号连接左右的值实现运算效果。对于一棵子树,它代表的就是原字符串的一个区间。同时,优先级也需要注意。假设对于某一棵子树内,既有+也有*也有^,那么根据优先级来,*的深度应该大于+的、^的深度应该大于*的,这样才能保证+是最后被计算到的。

然后本题只有+*,并且需要 $\bmod~10000$ 。

似乎表达式树的复杂度应该是 $O(|S|)$ 的,但是原谅我写假了,在每一层会多算几遍,但是过 $1e5$ 还是没问题的。

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