攝影或3C

Python 堆疊演算法入門：用 namedtuple 解析 PCBA 測試流程階層;章節編號連續化

本教學用 PCBA 測試流程作為情境，示範如何用堆疊（stack）在 O(n) 時間內：

  • 建立每個節點的父子關係（parent_index、children_count）
  • 生成章節式階層編號（如 1、1.2、2.1.3）

並以 collections.namedtuple 讓堆疊元素更易讀。

你會學到

  • 為什麼用堆疊處理階層資料
  • 如何用 namedtuple 優雅表達堆疊項目
  • 兩段小工具：建立父子關係、產生階層編號

示例資料：PCBA 測試流程
每個 heading 只有兩個欄位：

  • level：整數層級（1 是最高層）
  • title：標題文字
headings = [
    {"level": 1, "title": "PCBA 測試流程"},
    {"level": 2, "title": "目視檢查"},
    {"level": 2, "title": "上電前測試"},
    {"level": 1, "title": "功能測試"},
    {"level": 2, "title": "ICT（在線測試）"},
    {"level": 3, "title": "開路/短路檢查"},
    {"level": 3, "title": "元件值量測"},
    {"level": 2, "title": "FCT（功能測試）"},
    {"level": 3, "title": "通訊介面驗證"},
    {"level": 3, "title": "電源時序檢查"},
    {"level": 2, "title": "ATE（自動化設備測試）"},
]

為什麼用堆疊

  • 堆疊維護「從根到目前節點的路徑」。
  • 處理新節點時：
    • pop 掉所有層級 >= 當前層級的項目（它們不會是你的祖先）
    • 此時堆疊頂端就是你的父節點
    • push 當前節點進堆疊，供後續節點使用
  • 每個節點最多入堆一次、出堆一次，時間 O(n)。

用 namedtuple 表示堆疊項目

from collections import namedtuple
from typing import List, Optional

StackItem = namedtuple("StackItem", ["level", "index"])

常見陷阱與備註

  • 欄位名稱需要是有效的 Python 識別字，不能以數字開頭、不能有空白、不能與關鍵字衝突；否則在定義時就會報錯。
  • 欄位數與實例化傳入的參數數量必須一致。
  • namedtuple 預設是不可變的（immutable）；若需要可變欄位，考慮 dataclass。

namedtuple?

一、建立父子關係與 children_count

from collections import namedtuple
from typing import List, Optional

StackItem = namedtuple("StackItem", ["level", "index"])

def build_parent_child_relations(headings: List[dict]) -> None:
    """
    為每個 heading 建立：
      - parent_index：父節點在列表中的索引（根為 None）
      - children_count：子節點數
    原地修改；Time: O(n)，Space: O(d)（d 為最大深度）
    """
    stack: List[StackItem] = []

    # 初始化欄位
    for h in headings:
        h["parent_index"] = None
        h["children_count"] = 0

    for idx, h in enumerate(headings):
        lvl = h.get("level")
        if lvl is None:
            continue

        # 移除所有層級 >= 當前層級的項目
        while stack and stack[-1].level >= lvl:
            stack.pop()

        # 剩下頂端即父節點
        parent_idx: Optional[int] = stack[-1].index if stack else None
        h["parent_index"] = parent_idx

        # 父節點子數 +1
        if parent_idx is not None:
            headings[parent_idx]["children_count"] += 1

        # 當前節點入堆疊
        stack.append(StackItem(lvl, idx))

二、產生章節式階層編號 full_num_path
思路

  • 維護一個數字堆疊 path，例如 [2, 1, 3] 代表「2.1.3」。
  • 當前層比 path 長：補零再 +1
  • 當前層比 path 淺：pop 到同層再 +1
  • 同層：頂端 +1

實作

from typing import List

def assign_numbering(headings: List[dict]) -> None:
    """
    為每個 heading 產生 full_num_path（例如 1、1.2、2.1.3）。
    原地修改。
    """
    path: List[int] = []

    for h in headings:
        level = h.get("level")
        if level is None:
            h["full_num_path"] = ""
            continue

        # 補齊深度
        while len(path) < level:
            path.append(0)

        # 回退到目標層
        while len(path) > level:
            path.pop()

        # 目前層級計數 +1
        path[-1] += 1

        h["full_num_path"] = ".".join(str(x) for x in path)

完整示範：套用在 PCBA 測試流程

from collections import namedtuple
from typing import List, Optional

StackItem = namedtuple("StackItem", ["level", "index"])

def build_parent_child_relations(headings: List[dict]) -> None:
    stack: List[StackItem] = []
    for h in headings:
        h["parent_index"] = None
        h["children_count"] = 0
    for idx, h in enumerate(headings):
        lvl = h.get("level")
        if lvl is None:
            continue
        while stack and stack[-1].level >= lvl:
            stack.pop()
        parent_idx: Optional[int] = stack[-1].index if stack else None
        h["parent_index"] = parent_idx
        if parent_idx is not None:
            headings[parent_idx]["children_count"] += 1
        stack.append(StackItem(lvl, idx))

def assign_numbering(headings: List[dict]) -> None:
    path: List[int] = []
    for h in headings:
        level = h.get("level")
        if level is None:
            h["full_num_path"] = ""
            continue
        while len(path) < level:
            path.append(0)
        while len(path) > level:
            path.pop()
        path[-1] += 1
        h["full_num_path"] = ".".join(str(x) for x in path)

# 資料
headings = [
    {"level": 1, "title": "PCBA 測試流程"},
    {"level": 2, "title": "目視檢查"},
    {"level": 2, "title": "上電前測試"},
    {"level": 1, "title": "功能測試"},
    {"level": 2, "title": "ICT（在線測試）"},
    {"level": 3, "title": "開路/短路檢查"},
    {"level": 3, "title": "元件值量測"},
    {"level": 2, "title": "FCT（功能測試）"},
    {"level": 3, "title": "通訊介面驗證"},
    {"level": 3, "title": "電源時序檢查"},
    {"level": 2, "title": "ATE（自動化設備測試）"},
]

build_parent_child_relations(headings)
assign_numbering(headings)

for i, h in enumerate(headings):
    print(f'{i:>2}  L{h["level"]}  {h["full_num_path"]:>6}  '
          f'parent={h["parent_index"]}  children={h["children_count"]}  {h["title"]}')

輸出:

可能輸出解讀

  • 0 L1 1 parent=None children=2 PCBA 測試流程
    • PCBA 測試流程是根，孩子有「目視檢查」「上電前測試」
  • 3 L1 2 parent=None children=3 功能測試
    • 功能測試是另一個根層級，孩子有「ICT」「FCT」「ATE」
  • 5 L3 2.1.1 等
    • 代表「功能測試 > ICT > 開路/短路檢查」

常見變體與注意

  • 欄位名稱可依需求擴充，例如新增 id、slug。
  • 資料若跳級（例：從 level 1 直接到 level 3），請在導入前做資料校驗或補齊策略。
  • 若要輸出樹狀結構，可用 parent_index 重建 children 清單或直接在遍歷時建立 adjacency list。

重點總結

  • 堆疊法用 push/pop 追蹤階層路徑，處理階層資料直覺且高效。
  • namedtuple 讓堆疊項目具名屬性，兼具輕量與可讀性。
  • 兩個簡短函式即可完成 PCBA 流程的父子關係與章節式編號。

推薦hahow線上學習python: https://igrape.net/30afN

用一個單一遍歷（單迴圈）同時完成：

  • 父子關係（parent_index、children_count）
  • 連續的章節號 full_num_path（例如 1、1.2、2.3.1）

做法要點

  • 維護兩個結構：
    • stack: 保存從根到目前節點的路徑（含 level 與索引）。
    • path: 章節號數列（如 [2,1,3]）。
  • 對每個 heading：
    1. 依 level pop 掉不再是祖先的節點（更新 stack 與 path 同步回退）。
    2. 決定父節點（stack 頂端）。
    3. 對齊 path 長度到當前 level，補 0。
    4. 將 path[-1] += 1 取得新章節號。
    5. 設定 full_num_path、parent_index，並讓父節點 children_count += 1。
    6. 將當前節點 push 進 stack。

範例程式（單迴圈 O(n)）

from collections import namedtuple
from typing import List, Optional

StackItem = namedtuple("StackItem", ["level", "index"])

def build_all_in_one(headings: List[dict]) -> None:
    stack: List[StackItem] = []
    path: List[int] = []

    # 初始化欄位
    for h in headings:
        h["parent_index"] = None
        h["children_count"] = 0
        h["full_num_path"] = ""

    for i, h in enumerate(headings):
        level = h.get("level")
        if level is None:
            continue

        # 1) 回退到正確層級：同步調整 stack 與 path
        while stack and stack[-1].level >= level:
            stack.pop()
            path.pop()

        # 2) 決定父節點
        parent_idx: Optional[int] = stack[-1].index if stack else None
        h["parent_index"] = parent_idx
        if parent_idx is not None:
            headings[parent_idx]["children_count"] += 1

        # 3) 對齊 path 長度（處理跳級時會補 0）
        while len(path) < level:
            path.append(0)

        # 4) 目前層 +1，得到連續章節號
        path[-1] += 1
        h["full_num_path"] = ".".join(str(x) for x in path)

        # 5) 當前節點入堆疊
        stack.append(StackItem(level, i))

特性

  • 單迴圈、每個元素最多入堆一次出堆一次，時間 O(n)，空間 O(d)（d 為最大深度）。
  • 章節號天然連續：同層自動遞增；變深時從 1 開始（因為先補 0 再 +1）；變淺時回退到對應層後再 +1。
  • 可選擇在「補 0」處加入跳級校驗（當 level > prev_level + 1 時警告或拒絕）。

推薦hahow線上學習python: https://igrape.net/30afN

儲蓄保險王

儲蓄險是板主最喜愛的儲蓄工具,最喜愛的投資理財工具則是ETF,最喜愛的省錢工具則是信用卡

Leave a Comment
Share
Published by
儲蓄保險王
5 小時 ago

Recent Posts

Python 章節編號連續化教學：用程式為 Word 標題自動產生連續編號 full_num_path

本文教你如何將以 python...

6 小時 ago

Python: 用 zip 將「起點列表」轉成區間結束點：從 starts 推導 end ; next() 與 迭代器iter

目標情境你有一組按出現順序的區...

3 天 ago

Python 堆疊演算法實作：從扁平標題清單快速建立階層父子關係

前言在處理文件結構時（例如 W...

4 天 ago

Python 正則括號五兄弟：捕獲 / 非捕獲 / 命名 / 正向前瞻 / 負向前瞻 ( … )捕獲組, (?: … )非捕獲組, (?P … )命名捕獲組, (?= … )正向前瞻斷言, (?! … )負向前瞻斷言

目標： 1. 徹底理解五種常用...

5 天 ago

Python 字串切割的終極實戰指南: split / rsplit / partition / rpartition

目標讀者想徹底弄懂 split...

1 週 ago

Python 自省精簡示範：Frame 與 Code Object 入門; import inspect ; inspect.currentframe().f_code.co_name #動態取得function_name

在動態語言 Python 中，...

1 週 ago