#!/usr/bin/env python3
"""
EDEN STACK/QUEUE MASTERY
Fills the stack_queue gap
"""
import time

class EdenStack:
    """Stack with O(1) min/max tracking"""
    def __init__(self):
        self.stack = []
        self.min_stack = []
        self.max_stack = []
    
    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
        if not self.max_stack or val >= self.max_stack[-1]:
            self.max_stack.append(val)
    
    def pop(self):
        if not self.stack:
            return None
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()
        if val == self.max_stack[-1]:
            self.max_stack.pop()
        return val
    
    def get_min(self):
        return self.min_stack[-1] if self.min_stack else None
    
    def get_max(self):
        return self.max_stack[-1] if self.max_stack else None


def valid_parentheses(s):
    """Check if brackets are balanced"""
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in '({[':
            stack.append(char)
        elif char in ')}]':
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
    
    return len(stack) == 0


def eval_rpn(tokens):
    """Evaluate Reverse Polish Notation"""
    stack = []
    ops = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b)
    }
    
    for token in tokens:
        if token in ops:
            b, a = stack.pop(), stack.pop()
            stack.append(ops[token](a, b))
        else:
            stack.append(int(token))
    
    return stack[0]


def flatten_nested(nested):
    """Flatten nested list using stack"""
    stack = [nested]
    result = []
    
    while stack:
        item = stack.pop()
        if isinstance(item, list):
            stack.extend(reversed(item))
        else:
            result.append(item)
    
    return result


# Test
if __name__ == "__main__":
    print("🥞 EDEN STACK MASTERY")
    print("="*50)
    
    # MinStack test
    s = EdenStack()
    s.push(3); s.push(1); s.push(2)
    print(f"✅ MinStack: min={s.get_min()}, max={s.get_max()}")
    
    # Parentheses
    tests = ["()", "()[]{}", "(]", "([)]", "{[]}"]
    for t in tests:
        result = "✅" if valid_parentheses(t) else "❌"
        print(f"   {result} valid_parentheses('{t}')")
    
    # RPN
    start = time.perf_counter()
    rpn_result = eval_rpn(["2", "1", "+", "3", "*"])
    latency = (time.perf_counter() - start) * 1000
    print(f"✅ RPN ['2','1','+','3','*'] = {rpn_result}")
    print(f"⚡ Latency: {latency:.5f} ms")
    
    # Flatten
    nested = [[1, [2, 3]], [4, [5, [6]]]]
    print(f"✅ flatten({nested}) = {flatten_nested(nested)}")