// 第 7 周 – 实践课练习的参考答案
// 运行：java Exercises07.java
import java.util.ArrayDeque;

public class Exercises07 {

    // E1. 用栈把十进制转换成二进制（余数逆序就是结果）
    static String toBinary(int n) {
        if (n == 0) return "0";
        ArrayDeque<Integer> s = new ArrayDeque<>();
        while (n > 0) {
            s.push(n % 2);
            n = n / 2;
        }
        StringBuilder sb = new StringBuilder();
        while (!s.isEmpty()) sb.append(s.pop());
        return sb.toString();
    }

    // E2. 用栈把字符串逆序
    static String reverse(String str) {
        ArrayDeque<Character> s = new ArrayDeque<>();
        for (char c : str.toCharArray()) s.push(c);
        StringBuilder sb = new StringBuilder();
        while (!s.isEmpty()) sb.append(s.pop());
        return sb.toString();
    }

    // E3. 最小栈：push、pop 和 min 都是 O(1)。第二个栈存放到目前为止的最小值。
    static class MinStack {
        private final ArrayDeque<Integer> data = new ArrayDeque<>();
        private final ArrayDeque<Integer> mins = new ArrayDeque<>();

        void push(int x) {
            data.push(x);
            if (mins.isEmpty() || x <= mins.peek()) mins.push(x);
        }

        int pop() {
            int x = data.pop();
            if (x == mins.peek()) mins.pop();
            return x;
        }

        int min() { return mins.peek(); }
    }

    // E4. 文本编辑器中的撤销：每次操作之前的状态压入栈中
    static void undoDemo() {
        ArrayDeque<String> history = new ArrayDeque<>();
        String text = "";
        String[] typed = { "Hello", ", ", "World", "!!!" };
        for (String t : typed) {
            history.push(text);
            text = text + t;
            System.out.println("  typed: \"" + text + "\"");
        }
        for (int i = 0; i < 2; i++) {
            text = history.pop();
            System.out.println("  undo:  \"" + text + "\"");
        }
    }

    // E5. 代码阅读：字母 = 入栈，'*' = 出栈并输出
    static String trace(String ops) {
        ArrayDeque<Character> s = new ArrayDeque<>();
        StringBuilder out = new StringBuilder();
        for (char c : ops.toCharArray()) {
            if (c == '*') out.append(s.pop());
            else if (c != ' ') s.push(c);
        }
        return out.toString();
    }

    // E6. 反复删除相邻的相同字母对："abbaca" -> "ca"
    static String removeAdjacentDuplicates(String str) {
        ArrayDeque<Character> s = new ArrayDeque<>();
        for (char c : str.toCharArray()) {
            if (!s.isEmpty() && s.peek() == c) s.pop();
            else s.push(c);
        }
        StringBuilder sb = new StringBuilder();
        while (!s.isEmpty()) sb.append(s.pollLast()); // 自底向上
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println("E1. toBinary(50) = " + toBinary(50) + ", toBinary(13) = " + toBinary(13));
        System.out.println("E2. reverse(\"stack\") = " + reverse("stack"));
        MinStack ms = new MinStack();
        for (int x : new int[] { 5, 3, 7, 2, 8 }) ms.push(x);
        System.out.print("E3. min: " + ms.min());
        ms.pop();
        ms.pop();
        System.out.println(", after two pops: " + ms.min());
        System.out.println("E4. undo:");
        undoDemo();
        System.out.println("E5. trace(\"D A T * A * S * T R * U C * T\") = " + trace("D A T * A * S * T R * U C * T"));
        System.out.println("E6. removeAdjacentDuplicates(\"abbaca\") = " + removeAdjacentDuplicates("abbaca"));
    }
}