解題區/解題區 - UVa

UVa 10454 - Trexpression

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Solution

Problem

給一個只有加法、乘法和括弧的運算式，在不改變最後的答案下，有多少種不同的運算順序 (不同的 parse tree)。

Input

1
2
3
4
1+2+3+4
(1+2)+(3+4)
1+2+3*4
1+2+(3*4)

Output

1
2
3
4
5
1
2
2

Solution

類似矩陣鏈乘積的 O(n^3) 解法。

dp[l, r] 表示表達式 exp[l, r] 正確的方法數。當運算式存在加法時，不能拆分乘法運算。只剩下乘法運算時，才能拆分乘法運算。

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
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN = 256;
long long dp[MAXN][MAXN];
char s[MAXN];
long long dfs(int l, int r) {
    if (l == r)			return 1;
    if (dp[l][r] != -1)	return dp[l][r];
    long long &ret = dp[l][r];
    ret = 0;
    int left = 0, o1 = 0, o2 = 0;
    for (int i = l; i <= r; i++) {
        if (s[i] == '(')
            left++;
        else if (s[i] == ')')
            left--;
        else {
            if (left == 0) {
                if (s[i] == '+')	
                    o1 = 1;
                if (s[i] == '*')
                    o2 = 1;
            }				
        }
    }
    if (o1 == 0 && o2 == 0)
        ret += dfs(l+1, r-1);
    for (int i = l; i <= r; i++) {
        if (s[i] == '(')
            left++;
        else if (s[i] == ')')
            left--;
        else {
            if (left == 0) {
                if (s[i] == '+')
                    ret += dfs(l, i-1) * dfs(i+1, r);
                if (s[i] == '*' && o1 == 0)
                    ret += dfs(l, i-1) * dfs(i+1, r);
            }				
        }
    }
    return ret;
}
int main() {
    while (gets(s)) {
        memset(dp, -1, sizeof(dp));
        long long v = dfs(0, strlen(s) - 1);
        printf("%lld\n", v);
    }
    return 0;
}