上海计算机学会2020年6月月赛C++乙组T1文本编辑器
发布时间
阅读量：
阅读量
为了高效地模拟Gap buffer编辑器的行为并提取核心内容，我们采用两个栈的方法来实现文本编辑器的功能：
方法思路
我们使用两个栈来模拟Gap buffer的工作原理：
前边栈 (q) 存储位于光标的左侧部分的字符序列。
后边栈 (h) 存储位于光标的右侧部分的字符序列。
具体步骤如下：
题目描述
请实现一种名为 Gap buffer 的文本编辑器，在其运行初期，默认状态下该编辑器内的文本为空状态；为了便于操作者确定操作位置，在初始状态下，默认情况下该编辑器提供了一个光标来指示字符之间的间隙位置；其中所述光标一词具体定义为指向两个相邻字符之间空间位置的一个标记符号。
假设存在 n 项修改指令，请模拟编辑器对这些指令的处理流程，并最终输出编辑器的历史记录内容。
- 插入 操作：该操作需要指定一个字符
ch作为参数，并将该字符放置于光标左侧的位置； - 前进 操作：将光标向右移动一位，并在到达最末端时忽略此操作；
- 后退 操作：将光标向左移动一位，并在无法移动时（即已处于最左端）忽略此步骤；
- 删除 操作：删除位于光标右侧的所有字符，并在无字符可删除时（即已处于最右端）忽略此步骤。
输入格式
第一行：单个整数 n；
第二行到第 n+1 行：每行表示一个操作：
插入操作以字母i开头，并紧跟一个大写字母；确保所跟的字母是大写字母。删除操作仅使用一个d字符；前进操作仅采用一个f字符；后退操作仅使用一个b字符。
输出格式
单个字符串：表示编辑器最后所记录的文本内容。
数据范围
- 对于 30% 的数据，1≤n≤500；
- 对于 60% 的数据，1≤n≤50000；
- 对于 100% 的数据，1≤n≤500000。
样例数据
输入:
5
i H
i E
i L
i L
i O
输出:
HELLO
输入:
6
f
b
i A
b
i B
d
输出:
B
说明:
第一步的f和第二步的b都没有作用，接下来，每步结束后文本和光标的效果为：
A|
|A
B|A
B|
解析：可以使用链表模拟，详见代码：
#include <bits/stdc++.h>
using namespace std;
list <char> a;
list <char>::iterator p;
int main() {
int n;
cin >> n;
p = a.begin();
for (int i = 1; i <= n; i++) {
char c1;
cin >> c1;
if (c1 == 'i') {
char c2;
cin >> c2;
a.insert(p, c2);
} else if (c1 == 'd') {
if (!a.empty() && p != a.end())
p = a.erase(p);
} else if (c1 == 'f') {
if (p != a.end())
p++;
} else if (c1 == 'b') {
if (p != a.begin())
p--;
}
}
for (p = a.begin(); p != a.end(); p++) {
cout << *p;
}
return 0;
}另外一种方法可以用两个栈分别表示左边和右边的部分
遇到插入，则将字符压入前边的栈，
如遇到删除，则删除后边栈的栈顶，
光标左移，将前边栈的栈顶弹出，压入后边的栈，
光标右移，将后边栈的栈顶弹出，压入前边的栈。
最后将前边栈都弹出压入后边的栈，将后边的栈依次输出即可，
详见代码：
#include <bits/stdc++.h>
using namespace std;
stack <char> q;//光标前边的栈
stack <char> h;//光标后边的栈
int n;
char c;
int main() {
cin>>n;
while (n--){
char op;
cin>>op;
if (op=='i'){//插入
cin>>c;
q.push(c);//压入前边的栈
}else if (op=='d'){//删除
if (!h.empty()){//如果后边的栈非空
h.pop();//弹出后边的栈顶
}
}else if (op=='b'){//后退
if (!q.empty()){//如果前边的栈非空
c=q.top();//弹出前边的栈顶
q.pop();
h.push(c);//压入后边的栈
}
}else if (op=='f'){//前进
if (!h.empty()){//如果后边的栈非空
c=h.top();//弹出后边的栈顶
h.pop();
q.push(c);//压入前边的栈
}
}
}
while(!q.empty()){//将前边的栈，都压入后边的栈，即，相当于把光标移动到最前面
c=q.top();
q.pop();
h.push(c);
}
while(!h.empty()){//依次输出后边的栈顶，相当于光标后移的同时输出光标后边的字母
cout<<h.top();
h.pop();
}
return 0;
}全部评论 (0)
还没有任何评论哟~