資料結構與演算法 C# 實作系列：演示篇（二）─ 廣義樹遍歷與堆疊 RPN 計算機

編輯：關於C語言

前言

本文展示兩個經典演示：廣義樹四種遍歷模式 互動選擇，以及 堆疊實作逆波蘭表達式 (RPN) 計算機。

一、廣義樹遍歷互動演示

1.1 遍歷類型列舉

public enum TraversalType
{
    Breadth,     // 廣度優先
    PreDepth,    // 前序深度優先
    InDepth,     // 中序深度優先
    PostDepth    // 後序深度優先
}

1.2 使用者選擇與執行

public static void ShowGeneralTreeTraversal()
{
    Console.WriteLine("選擇遍歷模式：");
    Console.WriteLine("1. BreadthFirst - 廣度遍歷");
    Console.WriteLine("2. PreDepthFirst - 前序遍歷");
    Console.WriteLine("3. InDepthFirst - 中序遍歷");
    Console.WriteLine("4. PostDepthFirst - 後序遍歷");

    TraversalType type = 0;
    switch (Console.ReadLine())
    {
        case "1": type = TraversalType.Breadth; break;
        case "2": type = TraversalType.PreDepth; break;
        case "3": type = TraversalType.InDepth; break;
        case "4": type = TraversalType.PostDepth; break;
    }

    // 建構測試樹
    var A = new GeneralTree("A");
    var B = new GeneralTree("B");
    var C = new GeneralTree("C");
    var D = new GeneralTree("D");
    var E = new GeneralTree("E");
    var F = new GeneralTree("F");

    A.AttachSubtree(B); A.AttachSubtree(C); A.AttachSubtree(F);
    B.AttachSubtree(D); B.AttachSubtree(E);

    A.SetTraversalType(type);
    foreach (var node in A) // 透過 IEnumerable 實作
        Console.WriteLine(node);
}

二、堆疊 RPN 計算機

2.1 逆波蘭表示法

運算子後置，無需括號，適合堆疊計算。例：1 2 3 * + → 1 + (2 * 3) = 7。

2.2 完整實作

public static void ShowStackRpnCalculator()
{
    Console.WriteLine("輸入 RPN 運算式 (如 123*+)：");
    string expr = Console.ReadLine();

    var stack = new Stack();
    foreach (char c in expr)
    {
        switch (c)
        {
            case '*':
                stack.Push((int)stack.Pop() * (int)stack.Pop());
                break;
            case '+':
                stack.Push((int)stack.Pop() + (int)stack.Pop());
                break;
            default: // 數字字元
                stack.Push(int.Parse(c.ToString()));
                break;
        }
    }
    Console.WriteLine($"結果：{stack.Pop()}");
}