Starting from an empty string, m commands that change it are given in order.
There are four kinds of command.
'type s' appends s to the end of the string.
'erase k' deletes k characters from the end of the string. If the string is shorter than k, it deletes all of it.
'undo' reverts, among the edits that can be undone, the one that was made or redone most recently.
'redo' re-applies, among the edits that can be redone, the one that was undone most recently.
Here an edit means a type, or an erase that actually deleted at least one character.
An erase on an empty string does nothing and does not count as an edit.
When an edit is made, it becomes an edit that can be undone.
An edit reverted by undo can no longer be undone, and becomes an edit that can be redone.
An edit re-applied by redo can no longer be redone, and becomes an edit that can be undone again.
Undoing an erase appends the characters it deleted back to the end, and redoing it deletes the same number of characters from the end again.
When a new edit (a type, or an erase that deleted characters) is made, every edit that could be redone until then is gone.
undo and redo are not new edits, so they do not clear the edits that can be redone.
undo with nothing to undo, and redo with nothing to redo, do nothing.
Print the string after all commands.
If the string is empty, print EMPTY.
Input
The first line has m, followed by m lines with one command each. 1 ≤ m ≤ 10,000. In type, s is 1 to 5 lowercase English letters; in erase, k is an integer from 1 to 100.
Output
The final string (lowercase letters), or EMPTY
Example 1 · stdin
7
type hello
erase 2
type p
undo
undo
redo
type y
stdout
hely
Example 2 · stdin
5
type ab
undo
erase 3
redo
redo
stdout
ab
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Undo and redo are two stacks. An edit is pushed on the undo stack; undo pops its top, reverts it and pushes it on the redo stack; redo does the reverse. The last thing done is the first taken back (LIFO), which is exactly a stack. The trick is to record each edit as 'what was done': type records the appended string, and erase must record the string actually deleted, so undo can append it back (as many characters as were deleted, not the requested k). There are three common traps. ① Not clearing the redo stack after a new edit brings an abandoned branch of history back through redo. ② Recording an erase on an empty string as an edit lets a command that did nothing clear the redo stack and waste one undo. ③ Not putting a redone edit back on the undo stack makes it impossible to undo again. Each language handles stacks and strings its own way. Python uses a list with append/pop and a list of characters (text.extend(s), del text[len(text) - k:]); Java uses ArrayDeque<Edit> (push/pop), record Edit(boolean typed, String s), and cuts the end with StringBuilder.setLength. In C#, TryPop(out var e) on Stack<Edit> skips the empty stack for you, and StringBuilder.Length -= k cuts the end. C++ has std::stack (taking one out is top() then pop()), std::string::erase, and clearing is redo = {}. C keeps edits in an array of structs and only puts their numbers on the two stacks; the string is a fixed buffer plus a length variable, so cutting the end only lowers the length. JavaScript and TypeScript use arrays with push/pop (pop() on an empty array gives undefined) and slice, and clear with length = 0. Craykon stores an edit as a list like ["type", s], uses Add and RemoveAt(Count - 1) for the stacks, Clear() to empty them, and text.Substring(0, text.Length - k) to cut the end.
Pythonmain.py · 50 lines
import syslines = sys.stdin.read().split("\n")m = int(lines[0])text = [] # 지금 문자열(글자 목록: 끝에 붙이고 끝에서 지우기가 빠르다)undo = [] # 되돌릴 수 있는 편집들: ("type", 붙인 문자열) 또는 ("erase", 지운 문자열)redo = [] # 되돌렸다가 다시 할 수 있는 편집들def do(kind, s): if kind == "type": text.extend(s) else: del text[len(text) - len(s):]def undo_edit(kind, s): if kind == "type": del text[len(text) - len(s):] else: text.extend(s)for line in lines[1:1 + m]: parts = line.split() cmd = parts[0] if cmd == "type": do("type", parts[1]) undo.append(("type", parts[1])) redo.clear() # 새 편집을 하면 다시 하기 목록은 사라진다 elif cmd == "erase": k = min(int(parts[1]), len(text)) if k == 0: continue # 지운 글자가 없으면 편집이 아니다(기록도 안 하고 다시 하기도 그대로) removed = "".join(text[len(text) - k:]) do("erase", removed) undo.append(("erase", removed)) redo.clear() elif cmd == "undo": if undo: edit = undo.pop() undo_edit(*edit) redo.append(edit) elif cmd == "redo": if redo: edit = redo.pop() do(*edit) undo.append(edit)print("".join(text) if text else "EMPTY")
JavaScriptmain.js · 45 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const m = Number(lines[0]);let text = "";const undo = []; // 되돌릴 수 있는 편집들: { kind: "type" | "erase", s: 붙이거나 지운 문자열 }const redo = []; // 되돌렸다가 다시 할 수 있는 편집들function apply(edit) { if (edit.kind === "type") text += edit.s; else text = text.slice(0, text.length - edit.s.length);}function revert(edit) { if (edit.kind === "type") text = text.slice(0, text.length - edit.s.length); else text += edit.s;}for (let i = 1; i <= m; i++) { const [cmd, arg] = lines[i].trim().split(" "); if (cmd === "type") { const edit = { kind: "type", s: arg }; apply(edit); undo.push(edit); redo.length = 0; // 새 편집을 하면 다시 하기 목록은 사라진다 } else if (cmd === "erase") { const k = Math.min(Number(arg), text.length); if (k === 0) continue; // 지운 글자가 없으면 편집이 아니다(기록도 안 하고 다시 하기도 그대로) const edit = { kind: "erase", s: text.slice(text.length - k) }; apply(edit); undo.push(edit); redo.length = 0; } else if (cmd === "undo") { const edit = undo.pop(); if (edit !== undefined) { revert(edit); redo.push(edit); } } else if (cmd === "redo") { const edit = redo.pop(); if (edit !== undefined) { apply(edit); undo.push(edit); } }}console.log(text.length > 0 ? text : "EMPTY");
TypeScriptmain.ts · 52 lines
import { readFileSync } from "node:fs";interface Edit { kind: "type" | "erase"; s: string; // 붙이거나 지운 문자열}const lines: string[] = readFileSync(0, "utf8").split("\n");const m = Number(lines[0]);let text = "";const undo: Edit[] = []; // 되돌릴 수 있는 편집들const redo: Edit[] = []; // 되돌렸다가 다시 할 수 있는 편집들function apply(edit: Edit): void { if (edit.kind === "type") text += edit.s; else text = text.slice(0, text.length - edit.s.length);}function revert(edit: Edit): void { if (edit.kind === "type") text = text.slice(0, text.length - edit.s.length); else text += edit.s;}for (let i = 1; i <= m; i++) { const [cmd, arg] = lines[i].trim().split(" "); if (cmd === "type") { const edit: Edit = { kind: "type", s: arg }; apply(edit); undo.push(edit); redo.length = 0; // 새 편집을 하면 다시 하기 목록은 사라진다 } else if (cmd === "erase") { const k = Math.min(Number(arg), text.length); if (k === 0) continue; // 지운 글자가 없으면 편집이 아니다(기록도 안 하고 다시 하기도 그대로) const edit: Edit = { kind: "erase", s: text.slice(text.length - k) }; apply(edit); undo.push(edit); redo.length = 0; } else if (cmd === "undo") { const edit = undo.pop(); if (edit !== undefined) { revert(edit); redo.push(edit); } } else if (cmd === "redo") { const edit = redo.pop(); if (edit !== undefined) { apply(edit); undo.push(edit); } }}console.log(text.length > 0 ? text : "EMPTY");
JavaMain.java · 62 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;public class Main { // 편집 하나: 붙였는지(type) 지웠는지(erase)와 그 문자열 record Edit(boolean typed, String s) {} static StringBuilder text = new StringBuilder(); static void apply(Edit e) { if (e.typed()) text.append(e.s()); else text.setLength(text.length() - e.s().length()); } static void revert(Edit e) { if (e.typed()) text.setLength(text.length() - e.s().length()); else text.append(e.s()); } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int m = Integer.parseInt(in.readLine().trim()); ArrayDeque<Edit> undo = new ArrayDeque<>(); // 되돌릴 수 있는 편집들 ArrayDeque<Edit> redo = new ArrayDeque<>(); // 되돌렸다가 다시 할 수 있는 편집들 for (int i = 0; i < m; i++) { String[] parts = in.readLine().trim().split(" "); switch (parts[0]) { case "type" -> { Edit e = new Edit(true, parts[1]); apply(e); undo.push(e); redo.clear(); // 새 편집을 하면 다시 하기 목록은 사라진다 } case "erase" -> { int k = Math.min(Integer.parseInt(parts[1]), text.length()); if (k == 0) continue; // 지운 글자가 없으면 편집이 아니다(기록도 안 하고 다시 하기도 그대로) Edit e = new Edit(false, text.substring(text.length() - k)); apply(e); undo.push(e); redo.clear(); } case "undo" -> { if (!undo.isEmpty()) { Edit e = undo.pop(); revert(e); redo.push(e); } } case "redo" -> { if (!redo.isEmpty()) { Edit e = redo.pop(); apply(e); undo.push(e); } } } } System.out.println(text.length() > 0 ? text : "EMPTY"); }}
C#Main.cs · 70 lines
using System;using System.Collections.Generic;using System.Text;class Program{ // 편집 하나: 붙였는지(type) 지웠는지(erase)와 그 문자열 record Edit(bool Typed, string S); static readonly StringBuilder text = new StringBuilder(); static void Apply(Edit e) { if (e.Typed) text.Append(e.S); else text.Length -= e.S.Length; } static void Revert(Edit e) { if (e.Typed) text.Length -= e.S.Length; else text.Append(e.S); } static void Main() { int m = int.Parse(Console.ReadLine().Trim()); var undo = new Stack<Edit>(); // 되돌릴 수 있는 편집들 var redo = new Stack<Edit>(); // 되돌렸다가 다시 할 수 있는 편집들 for (int i = 0; i < m; i++) { string[] parts = Console.ReadLine().Trim().Split(' '); switch (parts[0]) { case "type": { var e = new Edit(true, parts[1]); Apply(e); undo.Push(e); redo.Clear(); // 새 편집을 하면 다시 하기 목록은 사라진다 break; } case "erase": { int k = Math.Min(int.Parse(parts[1]), text.Length); if (k == 0) break; // 지운 글자가 없으면 편집이 아니다(기록도 안 하고 다시 하기도 그대로) var e = new Edit(false, text.ToString(text.Length - k, k)); Apply(e); undo.Push(e); redo.Clear(); break; } case "undo": if (undo.TryPop(out var u)) { Revert(u); redo.Push(u); } break; case "redo": if (redo.TryPop(out var r)) { Apply(r); undo.Push(r); } break; } } Console.WriteLine(text.Length > 0 ? text.ToString() : "EMPTY"); }}
C++main.cpp · 64 lines
#include <algorithm>#include <iostream>#include <stack>#include <string>// 편집 하나: 붙였는지(type) 지웠는지(erase)와 그 문자열struct Edit { bool typed; std::string s;};std::string text;void apply(const Edit& e) { if (e.typed) text += e.s; else text.erase(text.size() - e.s.size());}void revert(const Edit& e) { if (e.typed) text.erase(text.size() - e.s.size()); else text += e.s;}int main() { int m; std::cin >> m; std::stack<Edit> undo; // 되돌릴 수 있는 편집들 std::stack<Edit> redo; // 되돌렸다가 다시 할 수 있는 편집들 for (int i = 0; i < m; i++) { std::string cmd; std::cin >> cmd; if (cmd == "type") { Edit e{true, ""}; std::cin >> e.s; apply(e); undo.push(e); redo = {}; // 새 편집을 하면 다시 하기 목록은 사라진다 } else if (cmd == "erase") { std::size_t k; std::cin >> k; k = std::min(k, text.size()); if (k == 0) continue; // 지운 글자가 없으면 편집이 아니다(기록도 안 하고 다시 하기도 그대로) Edit e{false, text.substr(text.size() - k)}; apply(e); undo.push(e); redo = {}; } else if (cmd == "undo") { if (!undo.empty()) { Edit e = undo.top(); undo.pop(); revert(e); redo.push(e); } } else if (cmd == "redo") { if (!redo.empty()) { Edit e = redo.top(); redo.pop(); apply(e); undo.push(e); } } } std::cout << (text.empty() ? "EMPTY" : text) << "\n";}
Cmain.c · 82 lines
#include <stdio.h>#include <string.h>#define MAXM 10000#define MAXTEXT 50000/* 편집 하나: 붙였는지(type) 지웠는지(erase)와 그 문자열(많아야 100자) */typedef struct { int typed; int len; char s[101];} Edit;static char text[MAXTEXT + 1];static int textLen = 0;static Edit edits[MAXM]; /* 편집은 명령마다 많아야 하나 생긴다 */static int undoStack[MAXM], undoTop = 0; /* 되돌릴 수 있는 편집들(edits의 번호) */static int redoStack[MAXM], redoTop = 0; /* 되돌렸다가 다시 할 수 있는 편집들 */static void apply(const Edit *e) { if (e->typed) { memcpy(text + textLen, e->s, e->len); textLen += e->len; } else { textLen -= e->len; }}static void revert(const Edit *e) { if (e->typed) { textLen -= e->len; } else { memcpy(text + textLen, e->s, e->len); textLen += e->len; }}int main(void) { int m, count = 0; char cmd[16], arg[16]; scanf("%d", &m); for (int i = 0; i < m; i++) { scanf("%15s", cmd); if (strcmp(cmd, "type") == 0) { scanf("%15s", arg); Edit *e = &edits[count]; e->typed = 1; e->len = (int)strlen(arg); memcpy(e->s, arg, e->len); apply(e); undoStack[undoTop++] = count++; redoTop = 0; /* 새 편집을 하면 다시 하기 목록은 사라진다 */ } else if (strcmp(cmd, "erase") == 0) { int k; scanf("%d", &k); if (k > textLen) k = textLen; if (k == 0) continue; /* 지운 글자가 없으면 편집이 아니다(기록도 안 하고 다시 하기도 그대로) */ Edit *e = &edits[count]; e->typed = 0; e->len = k; memcpy(e->s, text + textLen - k, k); apply(e); undoStack[undoTop++] = count++; redoTop = 0; } else if (strcmp(cmd, "undo") == 0) { if (undoTop > 0) { int id = undoStack[--undoTop]; revert(&edits[id]); redoStack[redoTop++] = id; } } else if (strcmp(cmd, "redo") == 0) { if (redoTop > 0) { int id = redoStack[--redoTop]; apply(&edits[id]); undoStack[undoTop++] = id; } } } text[textLen] = '\0'; puts(textLen > 0 ? text : "EMPTY"); return 0;}
Craykonmain.cray · 84 lines
// 편집 하나는 [종류, 문자열]: 종류는 "type"(붙임) 또는 "erase"(지움)text = "";undo = []; // 되돌릴 수 있는 편집들redo = []; // 되돌렸다가 다시 할 수 있는 편집들붙이기(s){ text = text + s;}끝지우기(개수){ text = text.Substring(0, text.Length - 개수);}하기(edit){ if (edit[0] == "type") { 붙이기(edit[1]); } else { 끝지우기(edit[1].Length); }}되돌리기(edit){ if (edit[0] == "type") { 끝지우기(edit[1].Length); } else { 붙이기(edit[1]); }}m = Console.ReadLine().Trim().ToNumber();for (i = 0; i < m; i++){ parts = Console.ReadLine().Trim().Split(" "); cmd = parts[0]; if (cmd == "type") { edit = ["type", parts[1]]; 하기(edit); undo.Add(edit); redo.Clear(); // 새 편집을 하면 다시 하기 목록은 사라진다 } else if (cmd == "erase") { k = Mathf.Min(parts[1].ToNumber(), text.Length); if (k > 0) { edit = ["erase", text.Substring(text.Length - k)]; 하기(edit); undo.Add(edit); redo.Clear(); } } else if (cmd == "undo") { if (undo.Count > 0) { edit = undo[undo.Count - 1]; undo.RemoveAt(undo.Count - 1); 되돌리기(edit); redo.Add(edit); } } else if (cmd == "redo") { if (redo.Count > 0) { edit = redo[redo.Count - 1]; redo.RemoveAt(redo.Count - 1); 하기(edit); undo.Add(edit); } }}Console.WriteLine(text.Length > 0 ? text : "EMPTY");