6 4 Broken_keyboard_(a.k.a._beiju_text_UVa11988) - nuaazdh/acm GitHub Wiki

##例题6-4 悲剧剧本（损坏的键盘）（Broken Keyboard (a.k.a. Beiju Text UVa 11988)

###问题 一个键盘的Home 和 End 键会自动按下，现在给定一个字符串（每个长度不超过 100000 ），字符串由字母、下环线和[、] 构成， [ 表示 Home， ] 表示 End，输出屏幕上实际显示的字符串

样例输入

This_is_a_[Beiju]_text 
[[]][][]Happy_Birthday_to_Tsinghua_University

样例输出

BeijuThis_is_a__text 
Happy_Birthday_to_Tsinghua_University

###分析 分析下，知道，要么就在字符串前端，要么就在字符串后端，可以用deque 实现，遇到[ 就标志下，然后到deque 前部插入字符， 若遇到 ] 就到尾部插入字符。

错！

a [ b c d [e ]

如果按照前端插入，则后插的反而在前面，但是实际不是这样。 要移动位置，看来不行，只能靠list 了。 但是要多个链表指针，表示当前应该插入的位置，头位置。

想到倒序扫描输出，即从末尾开始扫描，默认的 end_pos 在行末， 遇到 第一个 [ ，记下为位置 home_pos， 先输出 home_pos 到 end_pos 段的字符，然后调整两个位置；

###code in C++

#include <iostream>

int main() {
    std::string line;
    while (std::cin >> line) {
        int len = line.length(), end_pos = len;
        for (int i = len - 1; i >= 0; --i) {
            if (line[i] == '[') {
                for (int j = i + 1; j < end_pos; ++j) {
                    if (line[j] != ' ' && line[j] != ']' && line[j] != '[') {
                        std::cout << line[j];
                        line[j] = ' ';
                    }
                }
                end_pos = i;
            } else if (line[i] == ']') {
                end_pos = i;
            } else {

            }
        }
        for (int i = 0; i < len; ++i) {
            if (line[i] != ' ' && line[i] != ']' && line[i] != '[') {
                std::cout << line[i];
            }
        }
        std::cout << "\n";
    }
    return 0;
}

###点评 这个是一个可行解，但是效率太低，要扫描两次字符串，第一次从后向前，第二次从前向后。

###改进 我们想到这个其实可以用链表实现，原来链表是空的，如果这个字符是[，表示后续字符从头开始插入，如果是]表示后续字符从尾部插入。如果正常字符，从当前位置插入，注意当前位置不一定在链表的尾部。

可能想到链表就想到指针，其实不然。我们可以用数组实现链表，对字符数组 s[1,2,…n]，我们可以用 next[i] 表示s[i] 右侧的字符，即相当于 s[i]->next，只不过 next[i] 仍是一个 1~n 之间的整数，记录着下一个字符的下表而已。

###code in C

#include <string.h>

#define MAX_LEN 100010

int next[MAX_LEN];
char line[MAX_LEN];

int main() {
    int len, i, cur = 0, last = 0;
    while (scanf("%s", line + 1) != EOF) {
        len = strlen(line + 1);
        cur = 0, last = 0, next[0] = 0;
        for (i = 1; i <= len; ++i) {
            if (line[i] == '[') {
                cur = 0;
            } else if (line[i] == ']') {
                cur = last;
            } else {
                next[i] = next[cur];
                next[cur] = i;
                if (cur == last) last = i;
                cur = i;
            }
        }
        for (i = next[0]; i != 0; i = next[i]) {
            printf("%c", line[next[i]]);
        }
        printf("\n");
    }
    return 0;
}
⚠️ **GitHub.com Fallback** ⚠️