push(5)  push(8)  push(3)  pop()→3  push(1)  pop()→1

  +---+   +---+   +---+   +---+   +---+   +---+
  |   |   |   |   | 3 |   |   |   | 1 |   |   |
  +---+   +---+   +---+   +---+   +---+   +---+
  |   |   | 8 |   | 8 |   | 8 |   | 8 |   | 8 |
  +---+   +---+   +---+   +---+   +---+   +---+
  | 5 |   | 5 |   | 5 |   | 5 |   | 5 |   | 5 |
  +---+   +---+   +---+   +---+   +---+   +---+
   topo    topo    topo    topo    topo    topo

const std = @import("std");
const Allocator = std.mem.Allocator;

/// Pilha genérica baseada em array dinâmico.
pub fn Pilha(comptime T: type) type {
    return struct {
        const Self = @This();

        items: std.ArrayList(T),

        pub fn init(allocator: Allocator) Self {
            return .{ .items = std.ArrayList(T).init(allocator) };
        }

        pub fn deinit(self: *Self) void {
            self.items.deinit();
        }

        /// Empilha um elemento — O(1) amortizado.
        pub fn push(self: *Self, valor: T) !void {
            try self.items.append(valor);
        }

        /// Desempilha e retorna o topo — O(1).
        pub fn pop(self: *Self) ?T {
            return self.items.popOrNull();
        }

        /// Consulta o topo sem remover — O(1).
        pub fn topo(self: *const Self) ?T {
            if (self.items.items.len == 0) return null;
            return self.items.items[self.items.items.len - 1];
        }

        /// Verifica se está vazia.
        pub fn vazia(self: *const Self) bool {
            return self.items.items.len == 0;
        }

        /// Retorna o tamanho.
        pub fn tamanho(self: *const Self) usize {
            return self.items.items.len;
        }

        /// Limpa a pilha.
        pub fn limpar(self: *Self) void {
            self.items.clearRetainingCapacity();
        }
    };
}

// ==================== Aplicações ====================

/// Verifica se parênteses estão balanceados.
pub fn parentesesBalanceados(allocator: Allocator, expr: []const u8) !bool {
    var pilha = Pilha(u8).init(allocator);
    defer pilha.deinit();

    for (expr) |c| {
        switch (c) {
            '(', '[', '{' => try pilha.push(c),
            ')' => {
                if (pilha.pop()) |topo| {
                    if (topo != '(') return false;
                } else return false;
            },
            ']' => {
                if (pilha.pop()) |topo| {
                    if (topo != '[') return false;
                } else return false;
            },
            '}' => {
                if (pilha.pop()) |topo| {
                    if (topo != '{') return false;
                } else return false;
            },
            else => {},
        }
    }
    return pilha.vazia();
}

/// Converte expressão infixa para pós-fixa (notação polonesa reversa).
pub fn infixaParaPosfixa(allocator: Allocator, expr: []const u8) ![]u8 {
    var saida = std.ArrayList(u8).init(allocator);
    var ops = Pilha(u8).init(allocator);
    defer ops.deinit();

    for (expr) |c| {
        if (c >= '0' and c <= '9') {
            try saida.append(c);
        } else if (c == '(') {
            try ops.push(c);
        } else if (c == ')') {
            while (ops.topo()) |topo| {
                if (topo == '(') break;
                try saida.append(ops.pop().?);
            }
            _ = ops.pop(); // remove '('
        } else if (c == '+' or c == '-' or c == '*' or c == '/') {
            while (ops.topo()) |topo| {
                if (topo == '(' or precedencia(c) > precedencia(topo)) break;
                try saida.append(ops.pop().?);
            }
            try ops.push(c);
        }
    }
    while (ops.pop()) |op| try saida.append(op);

    return try saida.toOwnedSlice();
}

fn precedencia(op: u8) u8 {
    return switch (op) {
        '+', '-' => 1,
        '*', '/' => 2,
        else => 0,
    };
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // Uso básico
    var pilha = Pilha(i32).init(allocator);
    defer pilha.deinit();

    try pilha.push(10);
    try pilha.push(20);
    try pilha.push(30);

    try stdout.print("Topo: {?d}\n", .{pilha.topo()});
    try stdout.print("Pop: {?d}\n", .{pilha.pop()});
    try stdout.print("Pop: {?d}\n", .{pilha.pop()});
    try stdout.print("Tamanho: {d}\n", .{pilha.tamanho()});

    // Parênteses balanceados
    const exprs = [_][]const u8{ "((()))", "({[]})", "(()", "{[}]" };
    try stdout.print("\n=== Parênteses ===\n", .{});
    for (exprs) |e| {
        try stdout.print("\"{s}\" → {}\n", .{ e, try parentesesBalanceados(allocator, e) });
    }

    // Infixa para pós-fixa
    try stdout.print("\n=== Infixa → Pós-fixa ===\n", .{});
    const posfixa = try infixaParaPosfixa(allocator, "3+4*2/(1-5)");
    defer allocator.free(posfixa);
    try stdout.print("3+4*2/(1-5) → {s}\n", .{posfixa});
}