本檔收錄 5 題由易到難的練習。建議流程：先蓋住解答自己寫，卡住再看
「解題思路」，寫完對照「參考解答」。每題完整程式碼在 exercises/：
cc -std=c11 -Wall -Wextra -o /tmp/out exercises/ex1_stack_grow.c && /tmp/out練習 1：滿時自動倍增的動態堆疊（難度：基礎）
題目
為陣列堆疊加上 stack_grow：滿時用 realloc 把容量倍增。
從初始容量 2 開始 push 1..10，每次 push 印出目前 size/cap，
觀察成長事件；最後全部 pop 驗證 LIFO 順序。
realloc 失敗時不得洩漏原緩衝區。
解題思路
- 為什麼倍增而不是 +1：每次 +1 的話，第 n 次 push 都要搬 n
個元素，總成本 O(n²)。倍增讓搬移攤在指數成長的間隔上：
push n 個元素的總搬移量 ≤ 2n，攤銷 O(1)——這是
std::vector、Python list 等所有動態陣列的共同策略。 - realloc 的兩條安全規則：
- 結果先存暫時變數。
s->data = realloc(s->data, ...)在 失敗（回 NULL）時把唯一的舊指標蓋掉——那塊記憶體再也 free 不到，教科書級洩漏。 - realloc 可能搬家：舊指標一律作廢；程式印出buffer moved事件讓你親眼看到搬家發生。 - grow 的時機：
push開頭檢查top == cap才 grow—— 懶惰成長，pop 不縮容（實務上縮容要遲滯處理防抖動）。 - 結構設計：
top同時是「元素個數」與「下一個空位索引」， push 是data[top++]、pop 是data[--top]，對稱好記。
參考解答
/*
* ex1_stack_grow.c — 練習 1：滿時自動倍增的動態堆疊
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex1_stack_grow.c
* 執行：/tmp/out
*
* 為陣列堆疊加上 stack_grow：滿時用 realloc 倍增容量。
* 倍增（而非 +1）讓 push 的攤銷（amortized）成本是 O(1)。
*/
#include <stdio.h>
#include <stdlib.h>
struct stack {
int *data;
size_t top; /* 下一個空位的索引 = 目前元素數 */
size_t cap;
};
static void stack_init(struct stack *s, size_t initial_cap)
{
s->data = malloc(initial_cap * sizeof *s->data);
if (s->data == NULL) {
fprintf(stderr, "out of memory\n");
exit(1);
}
s->top = 0;
s->cap = initial_cap;
}
/*
* 倍增容量。realloc 重點：
* 1. 結果先存暫時變數——直接寫 s->data = realloc(s->data, ...)
* 失敗時舊指標被蓋掉，記憶體洩漏
* 2. realloc 可能搬家：舊指標一律作廢，透過 s->data 重新使用
*/
static void stack_grow(struct stack *s)
{
size_t new_cap = s->cap * 2;
int *p = realloc(s->data, new_cap * sizeof *p);
if (p == NULL) {
free(s->data);
fprintf(stderr, "out of memory growing stack\n");
exit(1);
}
printf(" [grow: %zu -> %zu slots%s]\n",
s->cap, new_cap, p == s->data ? "" : ", buffer moved");
s->data = p;
s->cap = new_cap;
}
static void push(struct stack *s, int v)
{
if (s->top == s->cap) /* 滿了才長大 */
stack_grow(s);
s->data[s->top++] = v;
}
static int pop(struct stack *s)
{
if (s->top == 0) {
fprintf(stderr, "stack underflow\n");
exit(1);
}
return s->data[--s->top];
}
static void stack_free(struct stack *s)
{
free(s->data);
s->data = NULL;
s->top = s->cap = 0;
}
int main(void)
{
struct stack s;
stack_init(&s, 2); /* 刻意從 2 開始，逼出幾次 grow */
printf("push 1..10 into a stack with initial capacity 2:\n");
for (int i = 1; i <= 10; i++) {
push(&s, i);
printf(" push %2d (size=%zu, cap=%zu)\n", i, s.top, s.cap);
}
printf("\npop everything (LIFO order):\n ");
while (s.top > 0)
printf(" %d", pop(&s));
printf("\n");
stack_free(&s);
return 0;
}程式碼講解
stack_grow的暫時變數p：失敗路徑先free(s->data)再退出 ——即使要死，也不留下洩漏（若程式要繼續跑，則保留舊緩衝區 並回報錯誤，由呼叫端決定）。sizeof *p而非sizeof(int)：型別改了配置大小自動跟上， 是 malloc/realloc 的防禦性寫法。- 輸出顯示 grow 發生在 push 3、5、9 之前——容量 2、4、8 的 邊界，成長次數是 log₂(n) 次，不是 n 次。
- 易錯處：把 grow 寫在 push 之後（先寫入越界位置再擴容），
heap 溢位；或忘記更新
s->cap導致每次 push 都 realloc。
範例輸出
push 1..10 into a stack with initial capacity 2:
push 1 (size=1, cap=2)
push 2 (size=2, cap=2)
[grow: 2 -> 4 slots]
push 3 (size=3, cap=4)
push 4 (size=4, cap=4)
[grow: 4 -> 8 slots, buffer moved]
push 5 (size=5, cap=8)
push 6 (size=6, cap=8)
push 7 (size=7, cap=8)
push 8 (size=8, cap=8)
[grow: 8 -> 16 slots, buffer moved]
push 9 (size=9, cap=16)
push 10 (size=10, cap=16)
pop everything (LIFO order):
10 9 8 7 6 5 4 3 2 1（buffer moved 是否出現取決於配置器當下的空間狀況。）
練習 2：用兩個堆疊實作佇列（難度：基礎）
題目
只用兩個堆疊實作 FIFO 佇列：enqueue 推入堆疊 A（in），
dequeue 時若堆疊 B（out）為空，把 A 全部倒進 B 再從 B pop。
測試需交錯進行 enqueue 與 dequeue，驗證輸出順序仍是 FIFO，
並印出「倒堆疊」事件觀察它何時發生。
解題思路
- 原理：負負得正。堆疊反轉順序（LIFO），倒兩次就恢復 原順序（FIFO）：
enqueue 1,2,3: pour（倒過去）: dequeue:
in: 3 in: (空) out: 3
2 out: 1 <- pop 端 2
1 2 （pop 得 1、2…FIFO!）
3- 倒的時機是效率關鍵：只在「out 空了且要 dequeue」時倒。 - 若每次 dequeue 都倒來倒去：O(n) 每次； - 懶惰法：每個元素一生至多被搬一次（in→out）， 攤銷 O(1)。
- 正確性論證：out 裡的元素永遠比 in 裡的早進入佇列 （它們是上一批倒過來的），所以 out 沒空之前絕不能碰 in—— 演算法的順序保證就從這條不變量來。
- q_empty：兩個堆疊都空才是空；只看 in 或只看 out 都是 bug。
- 測試設計：enqueue 1,2,3 → dequeue ×2 → enqueue 4,5 → 全部 dequeue。中途的 enqueue 4,5 進了 in，而 3 還在 out—— 輸出必須仍是 3,4,5，第二次 pour 發生在 3 被取走之後。
參考解答
/*
* ex2_queue_two_stacks.c — 練習 2：用兩個堆疊實作佇列
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex2_queue_two_stacks.c
* 執行：/tmp/out
*
* enqueue 一律推入 in 堆疊；dequeue 時若 out 空，
* 就把 in 全部倒進 out（順序反轉兩次 = 恢復 FIFO），再從 out pop。
* 每個元素最多被搬一次：攤銷 O(1)。
*/
#include <stdio.h>
#include <stdlib.h>
#define CAP 16
/* 簡單的固定容量 int 堆疊 */
struct stack {
int data[CAP];
int top; /* 元素個數 */
};
static void s_init(struct stack *s) { s->top = 0; }
static int s_empty(const struct stack *s) { return s->top == 0; }
static void s_push(struct stack *s, int v)
{
if (s->top == CAP) {
fprintf(stderr, "stack overflow\n");
exit(1);
}
s->data[s->top++] = v;
}
static int s_pop(struct stack *s)
{
if (s->top == 0) {
fprintf(stderr, "stack underflow\n");
exit(1);
}
return s->data[--s->top];
}
/* 佇列 = 兩個堆疊 */
struct queue {
struct stack in; /* enqueue 進這裡 */
struct stack out; /* dequeue 從這裡 */
};
static void q_init(struct queue *q)
{
s_init(&q->in);
s_init(&q->out);
}
static int q_empty(const struct queue *q)
{
return s_empty(&q->in) && s_empty(&q->out);
}
static void enqueue(struct queue *q, int v)
{
s_push(&q->in, v); /* O(1)：只推 in */
}
/*
* dequeue：out 有東西直接 pop；
* out 空了才把 in 整批倒過來（LIFO 反轉一次成 FIFO）。
* 「倒」的時機是關鍵：不能每次 enqueue/dequeue 都倒，
* 只在 out 耗盡時倒一次，每個元素一生至多搬一次。
*/
static int dequeue(struct queue *q)
{
if (s_empty(&q->out)) {
if (s_empty(&q->in)) {
fprintf(stderr, "queue underflow\n");
exit(1);
}
printf(" [pour: in -> out]\n");
while (!s_empty(&q->in))
s_push(&q->out, s_pop(&q->in));
}
return s_pop(&q->out);
}
int main(void)
{
struct queue q;
q_init(&q);
printf("enqueue 1, 2, 3:\n");
enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
printf("dequeue twice (FIFO order expected):\n");
printf(" dequeue = %d\n", dequeue(&q));
printf(" dequeue = %d\n", dequeue(&q));
printf("\nenqueue 4, 5 (interleaved with dequeues):\n");
enqueue(&q, 4);
enqueue(&q, 5);
printf("drain the queue:\n");
while (!q_empty(&q))
printf(" dequeue = %d\n", dequeue(&q));
printf("\nFIFO preserved: 1 2 3 4 5\n");
return 0;
}程式碼講解
dequeue的巢狀檢查順序：先看 out、再看 in、真的都空才報 underflow——與不變量「out 優先」一致。- pour 迴圈
while (!s_empty(&q->in)) s_push(&q->out, s_pop(&q->in));一行完成反轉——堆疊的 pop 順序天然是反的。 - 輸出中兩次
[pour]：第一次在最初的 dequeue（out 空）， 第二次在 3 取完、要拿 4 的時候——證明「懶惰倒」的行為。 - 這個結構在函數式語言叫 Banker's Queue，是純函數式資料 結構的經典；面試也常考（LeetCode 232）。
- 易錯處：dequeue 時 out 非空卻先倒 in——順序錯亂 （後來的元素插隊到 out 頂端）。
範例輸出
enqueue 1, 2, 3:
dequeue twice (FIFO order expected):
[pour: in -> out]
dequeue = 1
dequeue = 2
enqueue 4, 5 (interleaved with dequeues):
drain the queue:
dequeue = 3
[pour: in -> out]
dequeue = 4
dequeue = 5
FIFO preserved: 1 2 3 4 5練習 3：最小值堆疊（難度：進階）
題目
實作「最小值堆疊」：除 push/pop 外，get_min 回傳目前
堆疊中的最小值，三個操作都必須 O(1)。
push 序列 5 3 8 1 4，每步印出 get_min；再逐一 pop，
觀察最小值如何「回復」到先前的狀態。
解題思路
- 難點：單一變數記最小值不夠——pop 掉目前最小值後， 「前一個最小值」是誰？要 O(1) 回答就得把歷史存起來。
- 輔助堆疊：
mins與主堆疊同步成長，mins[i]= 「主堆疊長到第 i 層時，整體的最小值」：
push: 5 3 8 1 4
data: 5 3 8 1 4
mins: 5 3 3 1 1
^ 8 沒有更小，繼承前值 3- push：
mins推min(新值, mins 頂端)； pop：兩疊同步縮短——mins頂端自動變回舊的最小值， 這就是「歷史回復」的機制，pop 不需任何額外邏輯。 - get_min：讀
mins[top-1]，一次陣列存取。 - 空間換時間：多一倍空間換三個 O(1)。省空間的變體 （mins 只在「新最小值出現」時 push）留作延伸。
- 邊界：空堆疊的 get_min 是使用錯誤，明確報錯。
參考解答
/*
* ex3_min_stack.c — 練習 3：get_min 也是 O(1) 的最小值堆疊
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex3_min_stack.c
* 執行：/tmp/out
*
* 除 push/pop 外，get_min 也要 O(1)。
* 技巧：輔助堆疊 mins 與主堆疊同步——
* mins 頂端永遠是「目前整個堆疊的最小值」。
*/
#include <stdio.h>
#include <stdlib.h>
#define CAP 32
struct min_stack {
int data[CAP]; /* 主堆疊：真正的元素 */
int mins[CAP]; /* 輔助堆疊：每層的「當時最小值」 */
int top;
};
static void ms_init(struct min_stack *s) { s->top = 0; }
/*
* push：主堆疊照常推；
* mins 推「min(新值, 舊的最小值)」——每一層都記錄
* 「堆疊長到這裡時的最小值」，pop 時歷史自動回復。
*/
static void ms_push(struct min_stack *s, int v)
{
if (s->top == CAP) {
fprintf(stderr, "stack overflow\n");
exit(1);
}
int cur_min = (s->top == 0 || v < s->mins[s->top - 1])
? v
: s->mins[s->top - 1];
s->data[s->top] = v;
s->mins[s->top] = cur_min;
s->top++;
}
static int ms_pop(struct min_stack *s)
{
if (s->top == 0) {
fprintf(stderr, "stack underflow\n");
exit(1);
}
return s->data[--s->top]; /* mins 同步縮短，不需額外處理 */
}
static int ms_get_min(const struct min_stack *s)
{
if (s->top == 0) {
fprintf(stderr, "get_min on empty stack\n");
exit(1);
}
return s->mins[s->top - 1]; /* O(1)：直接看 mins 頂端 */
}
static void ms_dump(const struct min_stack *s)
{
printf(" data:");
for (int i = 0; i < s->top; i++)
printf(" %3d", s->data[i]);
printf("\n mins:");
for (int i = 0; i < s->top; i++)
printf(" %3d", s->mins[i]);
printf(" <- top\n");
}
int main(void)
{
struct min_stack s;
ms_init(&s);
int seq[] = { 5, 3, 8, 1, 4 };
printf("push sequence: 5 3 8 1 4\n\n");
for (size_t i = 0; i < sizeof seq / sizeof seq[0]; i++) {
ms_push(&s, seq[i]);
printf("push %d -> get_min = %d\n", seq[i], ms_get_min(&s));
}
printf("\nstack layers (mins[i] = min of data[0..i]):\n");
ms_dump(&s);
printf("\npop and watch the minimum recover:\n");
while (s.top > 0) {
int v = ms_pop(&s);
if (s.top > 0)
printf("pop %d -> get_min = %d\n", v, ms_get_min(&s));
else
printf("pop %d -> stack empty\n", v);
}
return 0;
}程式碼講解
- push 的三元運算式處理兩種情況：堆疊空（新值就是最小）、
新值 vs 舊最小取小者。
s->top == 0的檢查放在前面靠 短路求值保護mins[top-1]的存取。 ms_pop只有一行--top——兩個陣列共用同一個 top， 同步縮短是「免費」的。這是平行陣列（parallel array）設計的 甜頭。ms_dump印出兩排陣列讓不變量可視化：mins[i]恆等於min(data[0..i])，肉眼即可驗證。- pop 輸出展示「最小值回復」：pop 掉 1 之後 get_min 回到 3， 再 pop 到剩 5 時回到 5——歷史完整保存。
- 易錯處：只用一個
cur_min變數 + 重新掃描找次小值—— get_min 退化成 O(n)，不符題目要求。
範例輸出
push sequence: 5 3 8 1 4
push 5 -> get_min = 5
push 3 -> get_min = 3
push 8 -> get_min = 3
push 1 -> get_min = 1
push 4 -> get_min = 1
stack layers (mins[i] = min of data[0..i]):
data: 5 3 8 1 4
mins: 5 3 3 1 1 <- top
pop and watch the minimum recover:
pop 4 -> get_min = 1
pop 1 -> get_min = 3
pop 8 -> get_min = 3
pop 3 -> get_min = 5
pop 5 -> stack empty練習 4：RPN 計算機加上 %、neg、dup（難度：進階）
題目
為逆波蘭（RPN）計算機新增三個指令：
%：取餘（二元；除數為 0 要報錯，用整數語意）；neg：頂端取負（一元）；dup：複製頂端（堆疊操作，不是算術）。
測資需展示：17 5 % = 2、7 neg = -7、4 dup * = 16（平方）、
3 dup dup * * = 27（立方）、組合 10 3 % neg = -1。
解題思路
- RPN 求值的核心不變量：掃到數字就 push；掃到運算子就 pop 出運算元、算完 push 回去。運算式合法 ⇔ 結束時堆疊 恰剩一個值。
- 二元運算子的 pop 順序（老陷阱）：先 pop 出來的是 右運算元：
double b = pop(&s), a = pop(&s); /* b 右、a 左 */
push(&s, a - b); /* 17 5 - 是 17-5 */%的型別問題：C 的%只接受整數；堆疊存 double， 所以轉(long)再取餘。除數為 0 直接報錯（整數除以 0 是 UB， 不像浮點有 inf）。neg是一元：只 pop 一個。為什麼需要它？RPN 的數字 token-7可以直接寫，但「對運算結果取負」沒有中序的一元 減號可用，neg補上這個表達力。dup是堆疊操作：pop 一個、push 兩次。有了 dup， 「平方」不需要把運算元寫兩遍——這正是 Forth／PostScript 這類堆疊語言的日常詞彙（還有 swap、drop、over…）。- 收尾檢查：
s.top != 1時報「剩餘值」錯誤—— 抓出3 4（缺運算子）這類壞運算式。
參考解答
/*
* ex4_rpn_extended.c — 練習 4：RPN 計算機加上 %、neg、dup
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex4_rpn_extended.c
* 執行：/tmp/out
*
* 逆波蘭（後序）計算機：數字推入堆疊，運算子取出運算元再推回結果。
* 新增三個指令：
* % 取餘（二元；除數為 0 報錯）
* neg 頂端取負（一元）
* dup 複製頂端（堆疊操作）
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define CAP 64
struct stack {
double data[CAP];
int top;
};
static void push(struct stack *s, double v)
{
if (s->top == CAP) {
fprintf(stderr, "rpn: stack overflow\n");
exit(1);
}
s->data[s->top++] = v;
}
static double pop(struct stack *s)
{
if (s->top == 0) {
fprintf(stderr, "rpn: stack underflow (missing operand?)\n");
exit(1);
}
return s->data[--s->top];
}
/*
* 求值一個以空白分隔的 RPN 運算式。
* strtok 會改寫字串，呼叫端傳入可寫的複本。
*/
static double rpn_eval(char *expr)
{
struct stack s = { .top = 0 };
char *tok = strtok(expr, " ");
while (tok != NULL) {
if (isdigit((unsigned char)tok[0]) ||
(tok[0] == '-' && isdigit((unsigned char)tok[1]))) {
push(&s, atof(tok)); /* 數字（含負數字面值） */
} else if (strcmp(tok, "+") == 0) {
double b = pop(&s), a = pop(&s);
push(&s, a + b);
} else if (strcmp(tok, "-") == 0) {
double b = pop(&s), a = pop(&s);
push(&s, a - b); /* 順序：a 先進 = 左運算元 */
} else if (strcmp(tok, "*") == 0) {
double b = pop(&s), a = pop(&s);
push(&s, a * b);
} else if (strcmp(tok, "/") == 0) {
double b = pop(&s), a = pop(&s);
if (b == 0.0) {
fprintf(stderr, "rpn: division by zero\n");
exit(1);
}
push(&s, a / b);
} else if (strcmp(tok, "%") == 0) { /* 新增：取餘 */
double b = pop(&s), a = pop(&s);
if ((long)b == 0) {
fprintf(stderr, "rpn: modulo by zero\n");
exit(1);
}
push(&s, (double)((long)a % (long)b)); /* 整數語意 */
} else if (strcmp(tok, "neg") == 0) { /* 新增：取負 */
push(&s, -pop(&s)); /* 一元：只取一個 */
} else if (strcmp(tok, "dup") == 0) { /* 新增：複製頂端 */
double v = pop(&s);
push(&s, v);
push(&s, v);
} else {
fprintf(stderr, "rpn: unknown token '%s'\n", tok);
exit(1);
}
tok = strtok(NULL, " ");
}
if (s.top != 1) { /* 好的運算式恰剩一個值 */
fprintf(stderr, "rpn: %d values left on stack\n", s.top);
exit(1);
}
return pop(&s);
}
static void demo(const char *expr)
{
char buf[128];
strncpy(buf, expr, sizeof buf - 1);
buf[sizeof buf - 1] = '\0';
printf(" %-24s = %g\n", expr, rpn_eval(buf));
}
int main(void)
{
printf("RPN calculator with %%, neg, dup:\n\n");
demo("3 4 +"); /* 基本：3+4 */
demo("1 2 + 3 *"); /* (1+2)*3 */
demo("17 5 %"); /* 17 mod 5 = 2 */
demo("7 neg"); /* -7 */
demo("5 neg 3 +"); /* (-5)+3 = -2 */
demo("4 dup *"); /* 4*4 = 16：dup 做平方 */
demo("3 dup dup * *"); /* 3^3 = 27：dup 兩次做立方 */
demo("10 3 % neg"); /* -(10 mod 3) = -1 */
return 0;
}程式碼講解
- token 分類的第一個 if 同時接受
123與-7： 「-後面跟數字」是負數字面值，不是減號—— 這是 RPN tokenizer 唯一需要「往前看」的地方。 strtok會把分隔符改寫成'\0'，所以demo先把 字串常數複製進可寫的緩衝區——對字串常數呼叫 strtok 是 未定義行為。- 三個新指令各代表一類擴充：算術（
%）、一元運算（neg）、 堆疊操作（dup）——加新指令只是多一個else if分支， 核心迴圈完全不動。 3 dup dup * *的執行軌跡值得手演一次：[3]→[3 3]→[3 3 3]→[3 9]→[27]。- 易錯處：
a、b順序寫反——加法乘法看不出來， 減法除法取餘立刻出錯；測資17 5 %= 2（而非 5%17）就是驗這個。
範例輸出
RPN calculator with %, neg, dup:
3 4 + = 7
1 2 + 3 * = 9
17 5 % = 2
7 neg = -7
5 neg 3 + = -2
4 dup * = 16
3 dup dup * * = 27
10 3 % neg = -1練習 5：中序轉後序（shunting-yard）（難度：挑戰）
題目
實作 Dijkstra 的調度場（shunting-yard）演算法：把中序運算式
（支援非負整數、+ - * /、括號）轉成後序，再餵給 RPN 求值器
驗證結果。要求正確處理：
- 優先權（
1+2*3→1 2 3 * +）； - 左結合（
1-2-3→1 2 - 3 -，等於 -4 而非 2）； - 巢狀括號；
- 括號不平衡時回報語法錯誤。
解題思路
- 為什麼可行：後序運算式不需要括號與優先權——運算順序 完全由 token 排列決定。轉換的本質是把「何時執行運算子」 的資訊從語法規則翻譯成排列順序，而堆疊恰好是暫存 「還不能輸出的運算子」的地方。
- 規則表（整個演算法就這五條）：
| 看到 | 動作 |
|---|---|
| 數字 | 直接送輸出 |
| 運算子 op | 疊頂優先權 ≥ op 者依序彈出到輸出，然後 op 入疊 |
( |
入疊（在疊內優先權視為最低） |
) |
彈出到 ( 為止，( 丟棄 |
| 輸入結束 | 堆疊全部彈出（若遇 ( → 括號不平衡） |
- 為什麼是「≥」不是「>」：同優先權時先彈舊的 =
左結合。
1-2-3：第二個-進來時，疊裡的第一個-優先權相等 → 先彈出 → 輸出1 2 -之後才處理-3， 結果(1-2)-3。若用>就變右結合（1-(2-3)= 2，錯）。 (的兩個角色：入疊時像「屏障」——規則 2 的彈出遇到(要停（實作上給它優先權 0 並在 while 條件排除它）；)來時它是「配對終點」。- 錯誤偵測：
)彈到疊空還沒遇到(→ 多了右括號； 結尾彈出時遇到(→ 少了右括號。 - 驗證：轉出的後序字串直接餵 RPN 求值器（練習 4 的核心）， 對照心算結果——兩個演算法互相背書。
手演 (1+2)*3：
token 輸出 運算子疊
( (
1 1 (
+ 1 ( +
2 1 2 ( +
) 1 2 + (空) <- 彈到 ( 為止
* 1 2 + *
3 1 2 + 3 *
結尾 1 2 + 3 * (空)參考解答
/*
* ex5_shunting_yard.c — 練習 5：中序轉後序（shunting-yard）＋ RPN 求值
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex5_shunting_yard.c
* 執行：/tmp/out
*
* Dijkstra 的調度場演算法：
* 數字 -> 直接送輸出
* 運算子 -> 先把「優先權 >= 自己」的運算子從堆疊彈到輸出，再入疊
* ( -> 入疊
* ) -> 彈到 ( 為止（( 丟棄）
* 結尾 -> 堆疊全部彈出
* 轉出的後序字串餵給 RPN 求值器驗證。
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define CAP 64
#define OUTSZ 256
/* ---------- 運算子堆疊（char） ---------- */
static char op_stack[CAP];
static int op_top;
static void op_push(char c)
{
if (op_top == CAP) {
fprintf(stderr, "operator stack overflow\n");
exit(1);
}
op_stack[op_top++] = c;
}
static char op_pop(void) { return op_stack[--op_top]; }
static char op_peek(void) { return op_stack[op_top - 1]; }
/* 優先權：* / 高於 + -；( 在疊內優先權最低（擋住彈出） */
static int prec(char op)
{
switch (op) {
case '*': case '/': return 2;
case '+': case '-': return 1;
default: return 0; /* '(' */
}
}
/* ---------- 輸出緩衝：空白分隔的後序 token ---------- */
static void out_token(char *out, const char *tok)
{
if (out[0] != '\0')
strncat(out, " ", OUTSZ - strlen(out) - 1);
strncat(out, tok, OUTSZ - strlen(out) - 1);
}
/*
* 中序 -> 後序。支援非負整數、+ - * /、括號。
* 回傳 0 成功、-1 語法錯誤（括號不平衡）。
*/
static int infix_to_postfix(const char *infix, char *out)
{
out[0] = '\0';
op_top = 0;
for (const char *p = infix; *p != '\0'; ) {
if (*p == ' ') {
p++;
} else if (isdigit((unsigned char)*p)) {
char num[32];
int len = 0;
while (isdigit((unsigned char)*p) && len < 31)
num[len++] = *p++;
num[len] = '\0';
out_token(out, num); /* 數字直接輸出 */
} else if (*p == '(') {
op_push(*p);
p++;
} else if (*p == ')') {
/* 彈出到 ( 為止 */
while (op_top > 0 && op_peek() != '(') {
char op[2] = { op_pop(), '\0' };
out_token(out, op);
}
if (op_top == 0)
return -1; /* 沒有配對的 ( */
op_pop(); /* 丟棄 '(' */
p++;
} else if (strchr("+-*/", *p) != NULL) {
/*
* 左結合：疊頂優先權 >= 自己就先彈出。
* 這保證 1-2-3 轉成 1 2 - 3 -（由左往右算）。
*/
while (op_top > 0 && op_peek() != '(' &&
prec(op_peek()) >= prec(*p)) {
char op[2] = { op_pop(), '\0' };
out_token(out, op);
}
op_push(*p);
p++;
} else {
fprintf(stderr, "unexpected char '%c'\n", *p);
return -1;
}
}
while (op_top > 0) { /* 收尾：全部彈出 */
if (op_peek() == '(')
return -1; /* 多的 ( 沒關 */
char op[2] = { op_pop(), '\0' };
out_token(out, op);
}
return 0;
}
/* ---------- 簡易 RPN 求值器（同練習 4 的核心） ---------- */
static double rpn_eval(char *expr)
{
double st[CAP];
int top = 0;
for (char *tok = strtok(expr, " "); tok != NULL;
tok = strtok(NULL, " ")) {
if (isdigit((unsigned char)tok[0])) {
st[top++] = atof(tok);
} else {
double b = st[--top];
double a = st[--top];
switch (tok[0]) {
case '+': st[top++] = a + b; break;
case '-': st[top++] = a - b; break;
case '*': st[top++] = a * b; break;
case '/': st[top++] = a / b; break;
}
}
}
return st[0];
}
static void demo(const char *infix)
{
char postfix[OUTSZ];
if (infix_to_postfix(infix, postfix) != 0) {
printf(" %-18s -> syntax error\n", infix);
return;
}
char copy[OUTSZ];
strcpy(copy, postfix);
printf(" %-18s -> %-22s = %g\n", infix, postfix, rpn_eval(copy));
}
int main(void)
{
printf("shunting-yard: infix -> postfix -> evaluate\n\n");
demo("(1+2)*3"); /* 題目指定的例子 */
demo("1+2*3"); /* 優先權：乘先算 */
demo("1-2-3"); /* 左結合：(1-2)-3 = -4 */
demo("2*(3+4)-5");
demo("10/(5-3)");
demo("((2+3)*(4-1))"); /* 巢狀括號 */
demo("(1+2"); /* 括號不平衡：報錯 */
return 0;
}程式碼講解
prec()給(回 0：讓規則 2 的prec(op_peek()) >= prec(*p)自然擋住(（雙保險：while 條件也明確排除(）。- 多位數字的 tokenize：
while (isdigit...)收集連續數字字元—— 比逐字元處理的玩具版實用一大步。 - 輸出緩衝用「空白分隔字串」而非陣列：轉換結果本身就是 可讀的後序運算式，直接印出、直接餵求值器。
infix_to_postfix回傳錯誤碼而不是 exit：語法錯誤是 輸入的錯不是程式的錯，讓呼叫端決定如何處理 （demo 印syntax error繼續跑下一筆）。- RPN 求值器是練習 4 的精簡版——管線「轉換 → 求值」的兩級 各自可測，這是編譯器前端（parser → evaluator）的微縮模型。
- 易錯處一：規則 2 用
>導致左結合變右結合，1-2-3算出 2。 - 易錯處二：
)處理完忘記丟棄(（只彈不丟）， 之後的運算子被擋在假屏障後面，輸出順序全亂。
範例輸出
shunting-yard: infix -> postfix -> evaluate
(1+2)*3 -> 1 2 + 3 * = 9
1+2*3 -> 1 2 3 * + = 7
1-2-3 -> 1 2 - 3 - = -4
2*(3+4)-5 -> 2 3 4 + * 5 - = 9
10/(5-3) -> 10 5 3 - / = 5
((2+3)*(4-1)) -> 2 3 + 4 1 - * = 15
(1+2 -> syntax error常見錯誤解法對照
| 錯誤寫法 | 症狀 | 正解 |
|---|---|---|
s->data = realloc(s->data, ...) |
失敗時洩漏舊緩衝區 | 結果先存暫時變數（練習 1） |
| 容量 +1 成長 | push 總成本 O(n²) | 倍增，攤銷 O(1)（練習 1） |
| out 非空就倒 in | FIFO 順序錯亂 | out 耗盡才倒（練習 2） |
| 單變數記最小值 | pop 後找不回前最小 | 輔助堆疊存歷史（練習 3） |
| 二元運算 pop 順序反了 | 17 5 - 算成 -12 |
先 pop 的是右運算元（練習 4） |
shunting-yard 用 > 比優先權 |
左結合變右結合 | 用 >=（練習 5） |
) 彈完不丟 ( |
後續輸出全亂 | 配對後 ( 丟棄（練習 5） |