表达式树入门

严格来讲,我们所谈的表达式树是对一个计算式的中缀表达式所构造的二叉树形结构,在求解表达式的值时十分的方便。

对于一棵表达式树,其中每一个节点都表示一个字符,特别的是数值只会是叶子节点,这些数值由其祖先节点——均是“计算符号”的节点连接起来。而计算方式则是:
$$
\rm{S_u=calc(S_{v_1}, S_{v_2})}
$$
其中u为当前节点,calc函数的计算方式取决于点$u$上的符号。

从而只需要递归计算即可。

$1$ 递归建树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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 ;
}

其实也没啥好说的,这道题是NOIP2013普及组的表达式求值。然后建树的时候需要注意优先级……

但其实这个地方想说的不是这个东西,而是一个复杂度的问题。喜闻乐见的这个玩意儿的复杂度是$O(n^2)$的,但是在我加了

1
2
3
if ((In[k] == '+' || In[k] == '-') && k != l && !isop(In[k - 1])) { 
rt = k ; break ;
}//!

中的break之后,他就可以在400ms内的龟速把1e6的数据给艹过去了……也算是很迷

但听说似乎真正$O(|S|)$的建树其实只需要预处理一下每个位置之前最近的符号就好……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int build(int l, int r){
int rt = -1 ;
if (Code[r][1] >= l) rt = Code[r][1] ;
else if (Code[r][2] >= l) rt = Code[r][2] ;
if (rt > 0){
op[rt] = In[rt],
L[rt] = build(l, rt - 1),
R[rt] = build(rt + 1, r) ; return rt ;
}
op[r] = '?', sscanf(In + l, "%d", &val[r]) ; val[r] %= Mod ; return r ;
}
int dp(int x){
if (op[x] == '?') return val[x] ;
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 ;
return res ;
}
int main(){
cin >> (In + 1) ;
N = strlen(In + 1) ;
for (i = 1 ; i <= N ; ++ i){
if (In[i] == '+') Add = i ;
else if (In[i] == '*') Mul = i ;
Code[i][1] = Add, Code[i][2] = Mul ;
}
root = build(1, N) ; cout << dp(root) << endl ;
}

这似乎就是线性的了(flag * 1)。然而测了一下速发现:

$n^2$写法

$|S|$写法

似乎并没有什么区别……于是这就很佛了。。(fo * 1)

$2$ 用栈建树

这其实是在UOJ群里面iki9推荐的方式,我看到似乎兔队也是这么建的,于是就打算学一学。

然后其实也是蛮简单的,大概就是先用$|S|$的时间转化成后缀表达式,然后再用$|S|$的时间求出来。

转后缀表达式也挺简单,就是注意一定要是先计算优先级高的、后计算低的,所以我们需要一个优先级单调递减的栈来保存。

计算的时候用一个栈记录,每遇到一个计算符就弹出最顶上的俩数计算。因为后缀表达式的完备性所以一定是可行的。

好了我去写了……


……这踏马是什么操作啊喂…先贴代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
stack <char> stk ; stack <int> Ans ; int ans, i ;
char In[MAXN], op[MAXN], res[MAXN] ; int N, L, val[MAXN] ;

int calc(char x){
if (x =='(') return 1 ;
if (x =='+') return 2 ;
if (x =='-') return 2 ;
if (x =='*') return 3 ;
if (x =='/') return 3 ;
if (x =='^') return 4 ; return 0 ;
}
bool Comp(char a, char b){
return calc(a) >= calc(b) ;
}
int main(){
cin >> (In + 1), N = strlen(In + 1) ;
for (i = 1 ; i <= N ; ++ i){
int ret = 0 ;
if (isdigit(In[i])){
while (isdigit(In[i]))
ret = (ret << 1) + (ret << 3) + In[i] - '0', ++ i ;
i --, val[++ L] = ret, res[L] = 'N' ;
}
else if (In[i] == '(') stk.push(In[i]) ;
else if (In[i] == ')'){
while (stk.top() != '(')
res[++ L] = stk.top(), stk.pop() ;
stk.pop() ;
}
else {
while (!stk.empty() && Comp(stk.top(), In[i]))
res[++ L] = stk.top(), stk.pop() ;
stk.push(In[i]) ;
}
}
while (!stk.empty()) res[++ L] = stk.top(), stk.pop() ;
for (i = 1 ; i <= L ; ++ i){
if (!calc(res[i])) { Ans.push(val[i]) ; continue ; }
int p1 = Ans.top() ; Ans.pop() ; int p2 = Ans.top() ; Ans.pop() ;
if (calc(res[i]) == 2) {int p = (p1 + p2) % Mod ; Ans.push(p) ; }
else if (calc(res[i]) == 3) {int p = (p1 * p2) % Mod ; Ans.push(p) ; }
}
cout << Ans.top() % Mod << endl ; return 0 ;
}

再贴结果:

???

思考了思考,似乎刚才递归那种写法不是$O(|S |)$的?嗯,很有道理,那玩意儿复杂度应该是$O(|S|\log |S|)$的啊,毕竟tm终究是棵完全二叉树……

我佛了