C 語言實現科學計算器：中綴轉後綴 (Shunting-yard) 與堆疊求值完整原始碼解析

專案目標

解析並計算支援 + - * / ( ) 運算子、優先級與結合性的算術表達式 (如 3 + 4 * 2 / (1 - 5))。核心演算法：**Dijkstra Shunting-yard** 將中綴轉後綴 (RPN)，再以堆疊求值。

資料結構：動態堆疊

#define MAX_STACK 4000

typedef struct {
    char *data;      // 動態陣列
    int top;         // 下一個可寫入索引 (0 = 空)
    int capacity;
} Stack;

void Stack_Init(Stack *s, int cap) {
    s->data = malloc(cap);
    s->capacity = cap;
    s->top = 0;
}
void Stack_Free(Stack *s) { free(s->data); s->data = NULL; }

bool Stack_Empty(const Stack *s) { return s->top == 0; }
bool Stack_Full(const Stack *s) { return s->top >= s->capacity; }

void Stack_Push(Stack *s, char c) {
    if (Stack_Full(s)) { /* 擴容或錯誤 */ return; }
    s->data[s->top++] = c;
}
char Stack_Pop(Stack *s) {
    if (Stack_Empty(s)) return 0;
    return s->data[--s->top];
}
char Stack_Top(const Stack *s) {
    if (Stack_Empty(s)) return 0;
    return s->data[s->top - 1];
}

運算子優先級表 (數字越大優先級越高)

int Precedence(char op) {
    switch (op) {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        case '(': case ')': return 3; // 括號特殊處理
        default: return 0;
    }
}
bool IsOperator(char c) { return c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'; }

中綴 → 後綴 (Shunting-yard) 核心邏輯

// 輸入: 中綴字串 (以 '\0' 結尾)
// 輸出: 後綴字串 (空格分隔 token, 如 "3 4 2 * 1 5 - / +")
void InfixToPostfix(const char *infix, char *postfix) {
    Stack op_stack;
    Stack_Init(&op_stack, 256);
    int out_len = 0;

    for (int i = 0; infix[i]; i++) {
        char c = infix[i];
        if (c == ' ' || c == '\t') continue; // 忽略空白

        if (isdigit(c)) { // 數字 (支援多位數)
            int num = 0;
            while (isdigit(infix[i])) {
                num = num * 10 + (infix[i] - '0');
                i++;
            }
            i--; // 回退一位，外層 for 會 i++
            out_len += sprintf(postfix + out_len, "%d ", num);
        }
        else if (c == '(') {
            Stack_Push(&op_stack, c);
        }
        else if (c == ')') {
            while (!Stack_Empty(&op_stack) && Stack_Top(&op_stack) != '(') {
                postfix[out_len++] = Stack_Pop(&op_stack);
                postfix[out_len++] = ' ';
            }
            Stack_Pop(&op_stack); // 彈出 '('
        }
        else if (IsOperator(c)) {
            while (!Stack_Empty(&op_stack) && Stack_Top(&op_stack) != '(' &&
                   Precedence(Stack_Top(&op_stack)) >= Precedence(c)) {
                postfix[out_len++] = Stack_Pop(&op_stack);
                postfix[out_len++] = ' ';
            }
            Stack_Push(&op_stack, c);
        }
    }
    while (!Stack_Empty(&op_stack)) {
        postfix[out_len++] = Stack_Pop(&op_stack);
        postfix[out_len++] = ' ';
    }
    postfix[out_len] = '\0';
    Stack_Free(&op_stack);
}

後綴表達式求值

double EvalPostfix(const char *postfix) {
    Stack val_stack;
    Stack_Init(&val_stack, 256); // 這裡存 double，簡化用 char 陣列模擬，實際應用 double*
    // 為簡潔，改用靜態 double 陣列
    double vals[256];
    int top = 0;

    for (int i = 0; postfix[i]; i++) {
        if (postfix[i] == ' ') continue;
        if (isdigit(postfix[i])) {
            double num = 0;
            while (isdigit(postfix[i])) {
                num = num * 10 + (postfix[i] - '0');
                i++;
            }
            i--;
            vals[top++] = num;
        }
        else if (IsOperator(postfix[i])) {
            double b = vals[--top];
            double a = vals[--top];
            double res = 0;
            switch (postfix[i]) {
                case '+': res = a + b; break;
                case '-': res = a - b; break;
                case '*': res = a * b; break;
                case '/': res = a / b; break; // 應檢查除零
            }
            vals[top++] = res;
        }
    }
    Stack_Free(&val_stack);
    return vals[0];
}

完整主程式

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_EXPR 1024

int main() {
    char infix[MAX_EXPR];
    char postfix[MAX_EXPR * 2];

    printf("Scientific Calculator (type 'quit' to exit)\n");
    printf("Supported: + - * / ( )  multi-digit integers\n");

    while (1) {
        printf("> ");
        if (!fgets(infix, sizeof(infix), stdin)) break;
        infix[strcspn(infix, "\n")] = '\0'; // 去換行
        if (strcmp(infix, "quit") == 0) break;
        if (strlen(infix) == 0) continue;

        InfixToPostfix(infix, postfix);
        printf("Postfix: %s\n", postfix);
        double result = EvalPostfix(postfix);
        printf("Result: %.6f\n", result);
    }
    return 0;
}

測試案例

擴充方向

• 一元運算子：-5, +3 — 需在詞法分析區分一元/二元 - (前一 token 為運算子或 '(' 或開頭)。
• 冪次 ^：右結合，優先級高於 *，Shunting-yard 需判斷結合性。
• 函數呼叫：sin(30), max(1,2) — 視為運算子，遇 '(' 壓棧，遇 ')' 彈出至函數名。
• 變數/常數：pi, e, x — 符號表查找。
• 浮點數輸入：3.14 — 詞法分析支援小數點。
• 錯誤處理：括號不匹配、除零、語法錯誤位置回報。

現代 C++ 重構建議

#include 
#include 
#include 
#include 
#include 

enum class TokenType { Number, Plus, Minus, Mul, Div, LParen, RParen, End };
struct Token { TokenType type; double value; };

std::vector Lex(const std::string& s);           // 詞法分析
std::vector ToRPN(const std::vector&);    // Shunting-yard
double EvalRPN(const std::vector&);              // 求值
// 使用 std::variant 或結構體替代手工堆疊
// 利用 RAII 自動管理記憶體，編譯器檢查型別安全

結語

科學計算器是編譯器前端 (詞法分析、語法分析、AST、求值) 的縮影。用 C 語言手寫 Shunting-yard + 堆疊求值，能深入理解運算子優先級、結合性、括號處理、中綴/後綴轉換、堆疊機制。現代專案建議採用 Parser Combinator (如 PEGTL, mpark::parser) 或 Recursive Descent 產生 AST，再做常數摺疊、型別檢查、程式碼生成，構建完整編譯器前端管線。