// 第 7 周 – 实践课练习的参考答案
// 运行：go run ./w07/exercises
package main

import (
	"fmt"
	"strings"
)

// E1. 用栈把十进制转换成二进制
func toBinary(n int) string {
	if n == 0 {
		return "0"
	}
	var st []int
	for n > 0 {
		st = append(st, n%2)
		n /= 2
	}
	var sb strings.Builder
	for len(st) > 0 {
		fmt.Fprint(&sb, st[len(st)-1])
		st = st[:len(st)-1]
	}
	return sb.String()
}

// E2. 用栈把字符串逆序（按 rune 处理）
func reverse(s string) string {
	var st []rune
	for _, c := range s {
		st = append(st, c)
	}
	var sb strings.Builder
	for len(st) > 0 {
		sb.WriteRune(st[len(st)-1])
		st = st[:len(st)-1]
	}
	return sb.String()
}

// E3. 最小栈
type MinStack struct{ data, mins []int }

func (m *MinStack) Push(x int) {
	m.data = append(m.data, x)
	if len(m.mins) == 0 || x <= m.mins[len(m.mins)-1] {
		m.mins = append(m.mins, x)
	}
}

func (m *MinStack) Pop() int {
	x := m.data[len(m.data)-1]
	m.data = m.data[:len(m.data)-1]
	if x == m.mins[len(m.mins)-1] {
		m.mins = m.mins[:len(m.mins)-1]
	}
	return x
}

func (m *MinStack) Min() int { return m.mins[len(m.mins)-1] }

// E4. 撤销
func undoDemo() {
	var history []string
	text := ""
	for _, t := range []string{"Hello", ", ", "World", "!!!"} {
		history = append(history, text)
		text += t
		fmt.Printf("  typed: %q\n", text)
	}
	for i := 0; i < 2; i++ {
		text = history[len(history)-1]
		history = history[:len(history)-1]
		fmt.Printf("  undo:  %q\n", text)
	}
}

// E5. 代码阅读：字母 = 入栈，'*' = 出栈并输出
func trace(ops string) string {
	var st []rune
	var out strings.Builder
	for _, c := range ops {
		switch c {
		case ' ':
		case '*':
			out.WriteRune(st[len(st)-1])
			st = st[:len(st)-1]
		default:
			st = append(st, c)
		}
	}
	return out.String()
}

// E6. 反复删除相邻的相同元素对
func removeAdjacentDuplicates(s string) string {
	var st []rune
	for _, c := range s {
		if len(st) > 0 && st[len(st)-1] == c {
			st = st[:len(st)-1]
		} else {
			st = append(st, c)
		}
	}
	return string(st)
}

func main() {
	fmt.Println("E1. toBinary(50) =", toBinary(50), ", toBinary(13) =", toBinary(13))
	fmt.Println(`E2. reverse("stack") =`, reverse("stack"), `, reverse("数据结构") =`, reverse("数据结构"))
	var ms MinStack
	for _, x := range []int{5, 3, 7, 2, 8} {
		ms.Push(x)
	}
	fmt.Print("E3. min: ", ms.Min())
	ms.Pop()
	ms.Pop()
	fmt.Println(", after two pops:", ms.Min())
	fmt.Println("E4. undo:")
	undoDemo()
	fmt.Println(`E5. trace("D A T * A * S * T R * U C * T") =`, trace("D A T * A * S * T R * U C * T"))
	fmt.Println(`E6. removeAdjacentDuplicates("abbaca") =`, removeAdjacentDuplicates("abbaca"))
}