Advanced · Stacks and queues · 203 of 264
Undo
A tiny editor: type <word> adds the word to the end of the text, undo cancels the last type that is not already undone. Print the final text (words separated by spaces), or empty if there is none.
Input: n, then n commands. Output: the final text.
Examples
Input
4 type hello type world undo type there
Output
hello there
Input
2 type a undo
Output
empty
One more test checks other inputs when you press Check.
Stuck? The idea behind stacks and queues
A stack is last in, first out: a list's append() and pop(). A queue is first in, first out: collections.deque with append() and popleft().
Stacks match brackets and undo actions; queues serve things in the order they came.
stack = []
for ch in "(()":
if ch == "(":
stack.append(ch)
elif stack:
stack.pop()
print("left open:", len(stack))Watch for: pop() on an empty list stops the program: check the stack isn't empty first.