# 1. 函式呼叫堆疊
def a():
    print("In function a")
    b()
    print("Back in function a")

def b():
    print("In function b")
    c()
    print("Back in function b")

def c():
    print("In function c")

# 呼叫堆疊: main -> a() -> b() -> c()
# 返回順序: c() -> b() -> a() -> main

# 2. 瀏覽器的上一頁功能
browser_history = Stack()
browser_history.push("google.com")
browser_history.push("youtube.com")
browser_history.push("github.com")
# 按上一頁會回到 youtube.com

# 3. 文字編輯器的復原功能
undo_stack = Stack()
undo_stack.push("輸入 Hello")
undo_stack.push("輸入 World")
# Ctrl+Z 會復原最後的操作

class Stack:
    """使用 Python list 實作的 Stack"""
    
    def __init__(self):
        self.items = []
    
    def push(self, item):
        """將元素加入堆疊頂端 - O(1)"""
        self.items.append(item)
    
    def pop(self):
        """移除並回傳堆疊頂端元素 - O(1)"""
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.items.pop()
    
    def peek(self):
        """查看堆疊頂端元素 - O(1)"""
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.items[-1]
    
    def is_empty(self):
        """檢查堆疊是否為空 - O(1)"""
        return len(self.items) == 0
    
    def size(self):
        """回傳堆疊大小 - O(1)"""
        return len(self.items)
    
    def __str__(self):
        """視覺化顯示堆疊"""
        if self.is_empty():
            return "Stack(empty)"
        
        # 從上到下顯示
        result = "Stack (top to bottom):\n"
        for i in range(len(self.items) - 1, -1, -1):
            if i == len(self.items) - 1:
                result += f"  [{self.items[i]}] ← top\n"
            else:
                result += f"  [{self.items[i]}]\n"
        return result.strip()

# 使用範例
stack = Stack()
print(stack)  # Stack(empty)

# Push 操作
for i in [10, 20, 30]:
    stack.push(i)
    print(f"Pushed {i}")

print(stack)
# Stack (top to bottom):
#   [30] ← top
#   [20]
#   [10]

# Pop 操作
print(f"Popped: {stack.pop()}")  # 30
print(f"Peek: {stack.peek()}")    # 20
print(f"Size: {stack.size()}")    # 2

class Node:
    """節點類別"""
    def __init__(self, data):
        self.data = data
        self.next = None

class StackWithLinkedList:
    """使用 Linked List 實作的 Stack"""
    
    def __init__(self):
        self.top = None
        self._size = 0
    
    def push(self, item):
        """將元素加入堆疊頂端 - O(1)"""
        new_node = Node(item)
        new_node.next = self.top
        self.top = new_node
        self._size += 1
    
    def pop(self):
        """移除並回傳堆疊頂端元素 - O(1)"""
        if self.is_empty():
            raise IndexError("Stack is empty")
        
        data = self.top.data
        self.top = self.top.next
        self._size -= 1
        return data
    
    def peek(self):
        """查看堆疊頂端元素 - O(1)"""
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.top.data
    
    def is_empty(self):
        """檢查堆疊是否為空 - O(1)"""
        return self.top is None
    
    def size(self):
        """回傳堆疊大小 - O(1)"""
        return self._size
    
    def __str__(self):
        """視覺化顯示堆疊"""
        if self.is_empty():
            return "Stack(empty)"
        
        result = []
        current = self.top
        while current:
            result.append(str(current.data))
            current = current.next
        
        output = "Stack (top to bottom):\n"
        for i, item in enumerate(result):
            if i == 0:
                output += f"  [{item}] ← top\n"
            else:
                output += f"  [{item}]\n"
        return output.strip()

# 使用範例
stack = StackWithLinkedList()
for i in [1, 2, 3]:
    stack.push(i * 10)

print(stack)
print(f"Pop: {stack.pop()}")
print(f"After pop:\n{stack}")

class FixedStack:
    """固定大小的 Stack"""
    
    def __init__(self, capacity):
        self.capacity = capacity
        self.items = [None] * capacity
        self.top = -1
    
    def push(self, item):
        """將元素加入堆疊頂端 - O(1)"""
        if self.is_full():
            raise OverflowError("Stack is full")
        
        self.top += 1
        self.items[self.top] = item
    
    def pop(self):
        """移除並回傳堆疊頂端元素 - O(1)"""
        if self.is_empty():
            raise IndexError("Stack is empty")
        
        data = self.items[self.top]
        self.items[self.top] = None  # 清除參考
        self.top -= 1
        return data
    
    def peek(self):
        """查看堆疊頂端元素 - O(1)"""
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.items[self.top]
    
    def is_empty(self):
        """檢查堆疊是否為空 - O(1)"""
        return self.top == -1
    
    def is_full(self):
        """檢查堆疊是否已滿 - O(1)"""
        return self.top == self.capacity - 1
    
    def size(self):
        """回傳堆疊大小 - O(1)"""
        return self.top + 1
    
    def __str__(self):
        if self.is_empty():
            return "FixedStack(empty)"
        
        result = f"FixedStack(capacity={self.capacity}):\n"
        for i in range(self.top, -1, -1):
            if i == self.top:
                result += f"  [{self.items[i]}] ← top\n"
            else:
                result += f"  [{self.items[i]}]\n"
        return result.strip()

# 使用範例
fixed_stack = FixedStack(5)
print(f"Capacity: {fixed_stack.capacity}")

try:
    for i in range(6):
        fixed_stack.push(i)
        print(f"Pushed {i}, size: {fixed_stack.size()}")
except OverflowError as e:
    print(f"Error: {e}")

print(fixed_stack)

def is_balanced_parentheses(expression):
    """檢查括號是否平衡"""
    stack = Stack()
    
    # 定義配對關係
    pairs = {
        ')': '(',
        ']': '[',
        '}': '{'
    }
    
    for char in expression:
        if char in '([{':
            # 左括號，push 進 stack
            stack.push(char)
        elif char in ')]}':
            # 右括號，檢查配對
            if stack.is_empty():
                return False
            
            if stack.pop() != pairs[char]:
                return False
    
    # 最後 stack 應該是空的
    return stack.is_empty()

# 測試
test_cases = [
    ("()", True),
    ("()[]{}", True),
    ("([{}])", True),
    ("([)]", False),
    ("((", False),
    ("))", False),
    ("", True)
]

for expr, expected in test_cases:
    result = is_balanced_parentheses(expr)
    status = "✓" if result == expected else "✗"
    print(f"{status} '{expr}' → {result}")

def evaluate_postfix(expression):
    """
    計算後序表達式（逆波蘭表示法）
    例如: "2 3 + 5 *" = (2 + 3) * 5 = 25
    """
    stack = Stack()
    
    for token in expression.split():
        if token in '+-*/':
            # 運算符：pop 兩個運算元
            if stack.size() < 2:
                raise ValueError("Invalid expression")
            
            b = stack.pop()  # 注意順序
            a = stack.pop()
            
            if token == '+':
                result = a + b
            elif token == '-':
                result = a - b
            elif token == '*':
                result = a * b
            elif token == '/':
                result = a / b
            
            stack.push(result)
        else:
            # 運算元：push 進 stack
            stack.push(float(token))
    
    if stack.size() != 1:
        raise ValueError("Invalid expression")
    
    return stack.pop()

# 測試
expressions = [
    ("2 3 +", 5),              # 2 + 3
    ("2 3 + 5 *", 25),         # (2 + 3) * 5
    ("5 1 2 + 4 * + 3 -", 14), # 5 + ((1 + 2) * 4) - 3
]

for expr, expected in expressions:
    result = evaluate_postfix(expr)
    print(f"'{expr}' = {result} (expected: {expected})")

def infix_to_postfix(expression):
    """
    將中序表達式轉換為後序表達式
    例如: "2 + 3 * 5" → "2 3 5 * +"
    """
    precedence = {
        '+': 1,
        '-': 1,
        '*': 2,
        '/': 2,
        '^': 3
    }
    
    stack = Stack()
    output = []
    
    for token in expression.split():
        if token.isdigit():
            # 數字直接輸出
            output.append(token)
        elif token == '(':
            # 左括號 push 進 stack
            stack.push(token)
        elif token == ')':
            # 右括號：pop 直到遇到左括號
            while not stack.is_empty() and stack.peek() != '(':
                output.append(stack.pop())
            if not stack.is_empty():
                stack.pop()  # 移除左括號
        elif token in precedence:
            # 運算符：處理優先級
            while (not stack.is_empty() and 
                   stack.peek() != '(' and
                   stack.peek() in precedence and
                   precedence[stack.peek()] >= precedence[token]):
                output.append(stack.pop())
            stack.push(token)
    
    # Pop 剩餘的運算符
    while not stack.is_empty():
        output.append(stack.pop())
    
    return ' '.join(output)

# 測試
test_cases = [
    "2 + 3",                    # "2 3 +"
    "2 + 3 * 5",               # "2 3 5 * +"
    "( 2 + 3 ) * 5",           # "2 3 + 5 *"
    "2 + 3 * 5 - 4",           # "2 3 5 * + 4 -"
]

for infix in test_cases:
    postfix = infix_to_postfix(infix)
    print(f"Infix:   {infix}")
    print(f"Postfix: {postfix}")
    print(f"Result:  {evaluate_postfix(postfix)}\n")

class BrowserHistory:
    """瀏覽器歷史記錄管理"""
    
    def __init__(self):
        self.back_stack = Stack()      # 儲存歷史頁面
        self.forward_stack = Stack()   # 儲存前進頁面
        self.current_page = None
    
    def visit(self, url):
        """訪問新頁面"""
        if self.current_page:
            self.back_stack.push(self.current_page)
        
        self.current_page = url
        # 訪問新頁面時，清空 forward stack
        self.forward_stack = Stack()
        
        print(f"Visited: {url}")
    
    def back(self):
        """返回上一頁"""
        if self.back_stack.is_empty():
            print("No previous page")
            return None
        
        self.forward_stack.push(self.current_page)
        self.current_page = self.back_stack.pop()
        print(f"Back to: {self.current_page}")
        return self.current_page
    
    def forward(self):
        """前進到下一頁"""
        if self.forward_stack.is_empty():
            print("No forward page")
            return None
        
        self.back_stack.push(self.current_page)
        self.current_page = self.forward_stack.pop()
        print(f"Forward to: {self.current_page}")
        return self.current_page
    
    def show_status(self):
        """顯示當前狀態"""
        print(f"\nCurrent: {self.current_page}")
        print(f"Can go back: {not self.back_stack.is_empty()}")
        print(f"Can go forward: {not self.forward_stack.is_empty()}")

# 使用範例
browser = BrowserHistory()
browser.visit("google.com")
browser.visit("youtube.com")
browser.visit("github.com")
browser.show_status()

browser.back()  # 回到 youtube.com
browser.back()  # 回到 google.com
browser.forward()  # 前進到 youtube.com
browser.visit("stackoverflow.com")  # 清空 forward stack
browser.show_status()

class CallStack:
    """模擬函式呼叫堆疊"""
    
    def __init__(self):
        self.stack = Stack()
        self.depth = 0
    
    def call(self, function_name, params=None):
        """模擬函式呼叫"""
        self.stack.push({
            'function': function_name,
            'params': params,
            'depth': self.depth
        })
        print("  " * self.depth + f"→ Calling {function_name}({params})")
        self.depth += 1
    
    def return_from(self, function_name, result=None):
        """模擬函式返回"""
        if self.stack.is_empty():
            raise RuntimeError("Call stack is empty")
        
        self.depth -= 1
        call_info = self.stack.pop()
        
        if call_info['function'] != function_name:
            raise RuntimeError(f"Expected to return from {call_info['function']}")
        
        print("  " * self.depth + f"← Returning from {function_name}: {result}")
        return result
    
    def print_stack_trace(self):
        """印出堆疊追蹤"""
        print("\nStack Trace:")
        
        # 暫存所有元素
        temp = []
        while not self.stack.is_empty():
            temp.append(self.stack.pop())
        
        # 印出並恢復
        for i, call in enumerate(reversed(temp)):
            print(f"  {i}: {call['function']}({call['params']})")
        
        # 恢復 stack
        for call in reversed(temp):
            self.stack.push(call)

# 使用範例：模擬遞迴
def simulate_factorial(n):
    call_stack = CallStack()
    
    def factorial_with_stack(n):
        call_stack.call("factorial", n)
        
        if n <= 1:
            result = 1
        else:
            result = n * factorial_with_stack(n - 1)
        
        call_stack.return_from("factorial", result)
        return result
    
    try:
        result = factorial_with_stack(n)
        print(f"\nfactorial({n}) = {result}")
    except RecursionError:
        print("Stack overflow!")
        call_stack.print_stack_trace()

simulate_factorial(5)

class TextEditor:
    """支援 Undo/Redo 的文字編輯器"""
    
    def __init__(self):
        self.text = ""
        self.undo_stack = Stack()
        self.redo_stack = Stack()
    
    def write(self, text):
        """輸入文字"""
        # 儲存當前狀態到 undo stack
        self.undo_stack.push(self.text)
        
        # 清空 redo stack
        self.redo_stack = Stack()
        
        # 更新文字
        self.text += text
        print(f"Wrote: '{text}'")
        self.show()
    
    def delete(self, count):
        """刪除最後 count 個字元"""
        if count > len(self.text):
            count = len(self.text)
        
        # 儲存當前狀態
        self.undo_stack.push(self.text)
        self.redo_stack = Stack()
        
        # 刪除文字
        deleted = self.text[-count:]
        self.text = self.text[:-count]
        print(f"Deleted: '{deleted}'")
        self.show()
    
    def undo(self):
        """復原上一個操作"""
        if self.undo_stack.is_empty():
            print("Nothing to undo")
            return
        
        # 儲存當前狀態到 redo stack
        self.redo_stack.push(self.text)
        
        # 恢復前一個狀態
        self.text = self.undo_stack.pop()
        print("Undo performed")
        self.show()
    
    def redo(self):
        """重做上一個復原的操作"""
        if self.redo_stack.is_empty():
            print("Nothing to redo")
            return
        
        # 儲存當前狀態到 undo stack
        self.undo_stack.push(self.text)
        
        # 恢復下一個狀態
        self.text = self.redo_stack.pop()
        print("Redo performed")
        self.show()
    
    def show(self):
        """顯示當前文字"""
        print(f"Text: '{self.text}'")
        print(f"Can undo: {not self.undo_stack.is_empty()}")
        print(f"Can redo: {not self.redo_stack.is_empty()}\n")

# 使用範例
editor = TextEditor()
editor.write("Hello")
editor.write(" World")
editor.write("!")

editor.undo()  # 回到 "Hello World"
editor.undo()  # 回到 "Hello"

editor.redo()  # 前進到 "Hello World"
editor.write(" Python")  # 清空 redo stack

editor.delete(7)  # 刪除 " Python"
editor.undo()     # 恢復

def dfs_iterative(graph, start):
    """使用 Stack 實作的迭代式 DFS"""
    visited = set()
    stack = Stack()
    path = []
    
    stack.push(start)
    
    while not stack.is_empty():
        vertex = stack.pop()
        
        if vertex not in visited:
            visited.add(vertex)
            path.append(vertex)
            
            # 將鄰居加入 stack（反向加入以保持順序）
            for neighbor in reversed(graph[vertex]):
                if neighbor not in visited:
                    stack.push(neighbor)
    
    return path

# 測試圖
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

# 比較遞迴和迭代式 DFS
def dfs_recursive(graph, start, visited=None, path=None):
    """遞迴式 DFS（用於比較）"""
    if visited is None:
        visited = set()
        path = []
    
    visited.add(start)
    path.append(start)
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, path)
    
    return path

print("DFS Traversal:")
print(f"Iterative: {dfs_iterative(graph, 'A')}")
print(f"Recursive: {dfs_recursive(graph, 'A')}")

class MinStack:
    """支援 O(1) 時間取得最小值的 Stack"""
    
    def __init__(self):
        self.stack = Stack()
        self.min_stack = Stack()  # 儲存最小值
    
    def push(self, item):
        """Push - O(1)"""
        self.stack.push(item)
        
        # 更新最小值
        if self.min_stack.is_empty() or item <= self.min_stack.peek():
            self.min_stack.push(item)
    
    def pop(self):
        """Pop - O(1)"""
        if self.stack.is_empty():
            raise IndexError("Stack is empty")
        
        item = self.stack.pop()
        
        # 如果 pop 的是最小值，也要從 min_stack pop
        if item == self.min_stack.peek():
            self.min_stack.pop()
        
        return item
    
    def get_min(self):
        """取得最小值 - O(1)"""
        if self.min_stack.is_empty():
            raise ValueError("Stack is empty")
        return self.min_stack.peek()
    
    def peek(self):
        return self.stack.peek()
    
    def is_empty(self):
        return self.stack.is_empty()
    
    def __str__(self):
        return f"MinStack: {self.stack.items}, Min: {self.get_min() if not self.is_empty() else 'N/A'}"

# 測試
min_stack = MinStack()
values = [5, 2, 7, 2, 1, 8]

for val in values:
    min_stack.push(val)
    print(f"Push {val}: Min = {min_stack.get_min()}")

print()
while not min_stack.is_empty():
    print(f"Pop {min_stack.pop()}: Min = {min_stack.get_min() if not min_stack.is_empty() else 'N/A'}")

class QueueUsingTwoStacks:
    """使用兩個 Stack 實作 Queue"""
    
    def __init__(self):
        self.in_stack = Stack()   # 用於 enqueue
        self.out_stack = Stack()  # 用於 dequeue
    
    def enqueue(self, item):
        """入隊 - O(1)"""
        self.in_stack.push(item)
    
    def dequeue(self):
        """出隊 - 平均 O(1)，最壞 O(n)"""
        # 如果 out_stack 是空的，將 in_stack 的元素轉移過來
        if self.out_stack.is_empty():
            while not self.in_stack.is_empty():
                self.out_stack.push(self.in_stack.pop())
        
        if self.out_stack.is_empty():
            raise IndexError("Queue is empty")
        
        return self.out_stack.pop()
    
    def is_empty(self):
        return self.in_stack.is_empty() and self.out_stack.is_empty()
    
    def size(self):
        return self.in_stack.size() + self.out_stack.size()

# 測試
queue = QueueUsingTwoStacks()
for i in range(1, 4):
    queue.enqueue(i)
    print(f"Enqueued: {i}")

print(f"Dequeued: {queue.dequeue()}")  # 1
queue.enqueue(4)
print(f"Dequeued: {queue.dequeue()}")  # 2

# 1. 檢查字串是否為回文（使用 Stack）
def is_palindrome_with_stack(s):
    """使用 Stack 檢查回文"""
    stack = Stack()
    
    # 將前半部分 push 進 stack
    mid = len(s) // 2
    for i in range(mid):
        stack.push(s[i])
    
    # 如果長度是奇數，跳過中間字元
    start = mid + 1 if len(s) % 2 == 1 else mid
    
    # 比較後半部分
    for i in range(start, len(s)):
        if stack.is_empty() or stack.pop() != s[i]:
            return False
    
    return stack.is_empty()

# 2. 簡化檔案路徑
def simplify_path(path):
    """
    簡化 Unix 風格的檔案路徑
    例如: "/a/./b/../../c/" → "/c"
    """
    stack = Stack()
    parts = path.split('/')
    
    for part in parts:
        if part == '..':
            if not stack.is_empty():
                stack.pop()
        elif part and part != '.':
            stack.push(part)
    
    # 重建路徑
    result = []
    while not stack.is_empty():
        result.append(stack.pop())
    
    return '/' + '/'.join(reversed(result))

# 測試
test_paths = [
    "/home/",
    "/../",
    "/home//foo/",
    "/a/./b/../../c/",
]

for path in test_paths:
    print(f"'{path}' → '{simplify_path(path)}'")