HDU 4915 Parenthese sequence

HDU 4915 Parenthese sequence

題目鏈接

題意：給定一個有?的左右括號串，?能替代為'('或')'，問括號匹配是否唯一或多種或不可能

思路：先從右往左掃一邊，維護一個up， down表示當前位置右邊右括號剩余個數的上限和下限，如果維護完後起始位置的下限為0，那麼就是可以的，因為為0就代表沒有多余的右括號。然後在從左往右掃一遍，和上面一樣的處理，只是遇到每個問號的位置時，試一下左括號和右括號，如果都滿足，表示這個位置能放左右括號，是多種可能，如果所有?都只有唯一的方法，那麼答案就是唯一

代碼：

#include 
#include 
#include 
using namespace std;

const int N = 1000005;

char str[N];
int n, up[N], down[N], lup[N], ldown[N];

bool init() {
    up[n - 1] = down[n - 1] = 1;
    int cnt = 0;
    for (int i = n - 2; i >= 0; i--) {
	if (str[i] == ')') {
	    up[i] = up[i + 1] + 1;
	    down[i] = down[i + 1] + 1;
	}
	else if (str[i] == '(') {
	    up[i] = up[i + 1] - 1;
	    down[i] = down[i + 1] - 1;
	    if (down[i] < 0) {
		if (cnt == 0) return false;
		cnt--;
		if (up[i] == down[i]) up[i] = 1;
		down[i] = 1;
	    }
	}
	else {
	    up[i] = up[i + 1] + 1;
	    down[i] = down[i + 1] - 1;
	    if (down[i + 1] > 0 || cnt > 0) {
		down[i] = down[i + 1] - 1;
		if (down[i] < 0) {
		    down[i] = 1;
		    cnt--;
		}
	    }
	    else down[i] = down[i + 1] + 1;
	    cnt++;
	}
    }
    return (down[0] == 0);
}

void solve() {
    n = strlen(str);
    
    if (!init()) {
	printf("None\n");
	return;
    }
    lup[0] = ldown[9] = 1;
    for (int i = 1; i < n - 1; i++) {
	if (str[i] == '(') {
	    lup[i] = lup[i - 1] + 1;
	    ldown[i] = ldown[i - 1] + 1;
	}
	else if (str[i] == ')') {
	    ldown[i] = ldown[i - 1] - 1;
	    lup[i] = lup[i - 1] - 1;
	    if (ldown[i] < 0) {
		if (lup[i] == ldown[i]) lup[i] = 1;
		ldown[i] = 1;
	    }
	}
	else {
	    int flag = 0;
	    lup[i] = lup[i - 1] + 1;
	    ldown[i] = ldown[i - 1] - 1;
	    if (ldown[i] < 0) ldown[i] = 1;
	    int u, d;
	    u = lup[i - 1] + 1;
	    d = ldown[i - 1] + 1;
	    if (u >= down[i + 1] && d <= up[i + 1])
		flag++;
	    u = max(0, lup[i - 1] - 1);
	    d = max(0, ldown[i - 1] - 1);
	    if (u >= down[i + 1] && d <= up[i + 1])
		flag++;
	    if (flag == 2) {
		printf("Many\n");
		return;
	    }
	}
    }
    printf("Unique\n");
}

int main() {
    while (~scanf("%s", str)) {
	solve();
    }
    return 0;
}