Challenge: The Undo Button

Lab Java Beginner 10 points

A tiny editor gets commands: type w adds the word w at the end; undo removes the most recently typed word that is still there (if any). Print the final text with words separated by spaces, or empty.

Input

Line 1: q. Then q commands.

Output

The final text, or empty.

Example

Input

6
type I
type love
type cats
undo
type Java
undo

Output

I love

Sample input available Sample output available

Editor

Java

Hints

Each typed word is pushed on a stack; undo pops.

A stack gives words newest-first; descendingIterator() walks oldest-first. (An ArrayList with remove-at-end works too.)

Solution explanation

Every command is O(1). Undo is the classic stack use – your real editor works the same way.

Show solution

import java.util.ArrayDeque;
import java.util.Iterator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();
        ArrayDeque<String> words = new ArrayDeque<String>();
        for (int i = 0; i < q; i++) {
            String cmd = sc.next();
            if (cmd.equals("type")) words.push(sc.next());
            else if (!words.isEmpty()) words.pop();
        }
        if (words.isEmpty()) {
            System.out.println("empty");
            return;
        }
        StringBuilder sb = new StringBuilder();
        Iterator<String> it = words.descendingIterator();   // bottom of the stack first
        while (it.hasNext()) {
            if (sb.length() > 0) sb.append(' ');
            sb.append(it.next());
        }
        System.out.println(sb);
    }
}

Output

Answer