11988 - Broken Keyboard (a.k.a. Beiju Text) （UVA）

题目链接如下：

Online Judge

这道题折磨了我不少时间，开始比较直观的想法超时，后来看了下别人的思路修改后才AC。

刘汝佳的代码很简洁，UVa 11988 悲剧文本（四种方法）_uva11988-CSDN博客 这里有。

还有下面这个方法也非常巧妙：UVA 11988_uva - 11988-CSDN博客

我的代码如下：

#include 
#include 
#include 
// #define debug
 
int main(){
    #ifdef debug
    freopen("3.txt", "r", stdin);
    freopen("1.txt", "w", stdout);
    #endif
    std::string str;
    while (getline(std::cin, str)){
        int i, start, end, curr, s, t;
        std::vector<int> next(str.size());
        for (i = 0; i < str.size(); ++i){
            if (i == str.size() - 1 || str[i + 1] == '[' || str[i + 1] == ']'){
                next[i] = -1;
            } else {
                next[i] = i + 1;
            }
        }
        start = -1;
        i = 0;
        while (str[i] == '[' || str[i] == ']'){
            ++i;
        }
        start = i;
        for (; i < str.size(); ++i){
            if (str[i] == '[' || str[i] == ']'){
                break;
            }
        }
        end = i - 1;
        while (i < str.size() - 1){
            int temp = str[i] == '[' ? 1 : 0;
            ++i;
            s = i;
            for (; i < str.size(); ++i){
                if (str[i] == '[' || str[i] == ']'){
                    break;
                }
            }
            t = i - 1;
            if (s > t){
                continue;
            }
            if (temp){
                next[t] = start;
                start = s;
            } else {
                next[end] = s;
                end = t;
            }
        }
        curr = start;
        while (curr != -1){
            printf("%c", str[curr]);
            curr = next[curr];
        }
        printf("\n");
    }
    #ifdef debug
    fclose(stdin);
    fclose(stdout);
    #endif
    return 0;
}