首页 > itarticle > uva 10454 – trexpression

uva 10454 – trexpression

admin 11月 11, 2020 0

contents

Problem

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

Input

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

Output

Solution

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

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

#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("%lldn", v);
	}
	return 0;
}