從函數呼叫堆疊、瀏覽器前進後退、編輯器撤銷重做，到編譯器語法分析、表達式求值、DFS 圖遍歷，堆疊無處不在。本文實作多種堆疊變體，並深入演示中綴轉後綴（Shunting Yard）與後綴表達式求值——編譯器前端與計算器的核心算法。
public class ArrayStack {
private T[] _items;
private int _top; // 指向下一個可寫入位置，初始 0
public ArrayStack(int capacity) {
if (capacity <= 0) throw new ArgumentOutOfRangeException();
_items = new T[capacity];
_top = 0;
}
public int Count => _top;
public bool IsEmpty => _top == 0;
public void Push(T item) {
if (_top == _items.Length) throw new InvalidOperationException("Stack overflow");
_items[_top++] = item;
}
public T Pop() {
if (IsEmpty) throw new InvalidOperationException("Stack underflow");
T item = _items[--_top];
_items[_top] = default; // 釋放引用助 GC
return item;
}
public T Peek() => IsEmpty ? throw new InvalidOperationException() : _items[_top - 1];
}
public class LinkedStack {
private class Node {
public T Value;
public Node Next;
public Node(T val, Node next) { Value = val; Next = next; }
}
private Node _head;
public int Count { get; private set; }
public bool IsEmpty => _head == null;
public void Push(T item) {
_head = new Node(item, _head);
Count++;
}
public T Pop() {
if (IsEmpty) throw new InvalidOperationException();
T val = _head.Value;
_head = _head.Next;
Count--;
return val;
}
public T Peek() => IsEmpty ? throw new InvalidOperationException() : _head.Value;
}
public class DualArrayStack {
private double[] _items;
private int _top1; // 堆疊1從左向右增長
private int _top2; // 堆疊2從右向左增長
public DualArrayStack(int totalCapacity) {
_items = new double[totalCapacity];
_top1 = 0;
_top2 = totalCapacity - 1;
}
public void Push1(double v) {
if (_top1 > _top2) throw new InvalidOperationException("Stack overflow");
_items[_top1++] = v;
}
public double Pop1() => _items[--_top1];
public void Push2(double v) {
if (_top1 > _top2) throw new InvalidOperationException("Stack overflow");
_items[_top2--] = v;
}
public double Pop2() => _items[++_top2];
}
中綴：3 + 4 * 2 / (1 - 5)→ 後綴：3 4 2 * 1 5 - / +
public static class InfixToPostfix {
private static int Precedence(char op) => op switch {
'+' or '-' => 1,
'*' or '/' => 2,
'^' => 3,
_ => 0
};
public static string Convert(string infix) {
var output = new List();
var ops = new Stack();
int i = 0, n = infix.Length;
while (i < n) {
char c = infix[i];
if (char.IsWhiteSpace(c)) { i++; continue; }
// 數字（含多位數、小數）
if (char.IsDigit(c) || c == '.') {
int start = i;
while (i < n && (char.IsDigit(infix[i]) || infix[i] == '.')) i++;
output.Add(infix.Substring(start, i - start));
continue;
}
// 左括號
if (c == '(') { ops.Push(c); i++; continue; }
// 右括號：彈出至左括號
if (c == ')') {
while (ops.Count > 0 && ops.Peek() != '(')
output.Add(ops.Pop().ToString());
if (ops.Count == 0) throw new ArgumentException("括號不匹配");
ops.Pop(); // 丟棄左括號
i++; continue;
}
// 運算子
if ("+-*/^".Contains(c)) {
while (ops.Count > 0 && ops.Peek() != '(' &&
Precedence(ops.Peek()) >= Precedence(c))
output.Add(ops.Pop().ToString());
ops.Push(c);
i++; continue;
}
throw new ArgumentException($"非法字元: {c}");
}
while (ops.Count > 0) {
if (ops.Peek() == '(') throw new ArgumentException("括號不匹配");
output.Add(ops.Pop().ToString());
}
return string.Join(" ", output);
}
}
public static class PostfixEvaluator {
public static double Evaluate(string postfix) {
var stack = new Stack();
var tokens = postfix.Split(' ', StringSplitOptions.RemoveEmptyEntries);
foreach (string tok in tokens) {
if (double.TryParse(tok, out double num)) {
stack.Push(num);
} else if (tok.Length == 1 && "+-*/^".Contains(tok)) {
if (stack.Count < 2) throw new ArgumentException("運算元不足");
double b = stack.Pop(); // 右運算元
double a = stack.Pop(); // 左運算元
double result = tok[0] switch {
'+' => a + b,
'-' => a - b,
'*' => a * b,
'/' => b == 0 ? throw new DivideByZeroException() : a / b,
'^' => Math.Pow(a, b),
_ => throw new ArgumentException($"未知運算子: {tok}")
};
stack.Push(result);
} else {
throw new ArgumentException($"無效 Token: {tok}");
}
}
if (stack.Count != 1) throw new ArgumentException("運算式錯誤");
return stack.Pop();
}
}
string infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3";
string postfix = InfixToPostfix.Convert(infix);
Console.WriteLine($"中綴: {infix}");
Console.WriteLine($"後綴: {postfix}");
// 輸出: 3 4 2 * 1 5 - 2 3 ^ ^ / +
double result = PostfixEvaluator.Evaluate(postfix);
Console.WriteLine($"結果: {result}"); // 約 3.000122
| 主題 | 關鍵點 |
|---|---|
| 一元運算子（負號） | 需區分一元 - 與二元 -：掃描時若 - 前為運算子/左括號/開頭，視為一元，可轉為 0 - operand 或引入 ~ 符號 |
| 函數支援 (sin, max 等) | Shunting Yard 擴展：函數名入堆疊，遇逗號彈出至左括號，遇右括號彈出函數名輸出 |
| 右結合冪運算 ^ | 優先序相同時，右結合不彈出（> 而非 >=），上述代碼已處理 |
| 錯誤處理 | 括號不匹配、運算元不足、除零、非法字元、最終堆疊非單一值 |
| 效能優化 | 字串分割分配記憶體，高頻計算可用 Span 手寫 Tokenizer 避免分配 |
| 實務替代 | 生產環境建議 NCalc、Flee、Jace.NET 等成熟表達式引擎 |
從 ArrayStack、LinkedStack、DualArrayStack 三種底層實作，到 InfixToPostfix.Convert 與 PostfixEvaluator.Evaluate 兩大核心算法，本文完整串聯了堆疊資料結構 → 表達式轉換 → 表達式求值的完整鏈路。掌握 Shunting Yard 算法細節（優先序、結合性、括號、一元運算子、函數），即可自行實作計算器、DSL 解析器、配置語言直譯器等編譯器前端核心組件。
