C 語言實作四則運算表達式求值：雙堆疊演算法完整解析與代碼

演算法核心：Dijkstra 雙堆疊法 (Shunting-yard 變體)

維護兩個堆疊：

• 運算元堆疊 (valStack)：存放數值 (double)。
• 運算子堆疊 (opStack)：存放運算子字元 (+, -, *, /, (, ))。

處理流程

1. 掃描字串，跳過空白。
2. 若為數字（含小數點），解析完整數值壓入 valStack。
3. 若為運算子 op：
   • 若 opStack 為空或頂端為 (，直接壓入。
   • 否則比較優先序：priority(op) > priority(top) 則壓入；否則彈出頂端運算子 topOp、彈出兩個運算元 b, a、計算 a topOp b 壓回 valStack，重複直到可壓入 op。
4. 若為 (，直接壓入 opStack。
5. 若為 )，持續彈出計算直到遇到 ( 並丟棄它。
6. 掃描結束，將 opStack 剩餘運算子依序彈出計算。
7. valStack 頂端即為結果。

優先序定義

int priority(char op) {
    switch (op) {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        default: return 0;
    }
}

完整可編譯 C 代碼 (C99)

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

#define MAX 1024

double valStack[MAX]; int vtop = 0;
char   opStack[MAX];  int otop = 0;

void pushVal(double v) { valStack[vtop++] = v; }
double popVal() { return valStack[--vtop]; }
void pushOp(char c) { opStack[otop++] = c; }
char popOp() { return opStack[--otop]; }
char peekOp() { return otop ? opStack[otop-1] : 0; }
int isEmptyOp() { return otop == 0; }

int priority(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

double apply(char op, double a, double b) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return b ? a / b : NAN;
    }
    return NAN;
}

double evaluate(const char *expr) {
    vtop = otop = 0;
    const char *p = expr;
    while (*p) {
        if (isspace(*p)) { p++; continue; }
        if (isdigit(*p) || *p == '.') {
            char *end;
            double v = strtod(p, &end);
            pushVal(v);
            p = end;
        } else if (*p == '(') {
            pushOp(*p++);
        } else if (*p == ')') {
            while (!isEmptyOp() && peekOp() != '(') {
                char op = popOp();
                double b = popVal(), a = popVal();
                pushVal(apply(op, a, b));
            }
            if (!isEmptyOp() && peekOp() == '(') popOp(); // discard '('
            p++;
        } else if (strchr("+-*/", *p)) {
            char op = *p++;
            while (!isEmptyOp() && peekOp() != '(' && priority(op) <= priority(peekOp())) {
                char topOp = popOp();
                double b = popVal(), a = popVal();
                pushVal(apply(topOp, a, b));
            }
            pushOp(op);
        } else {
            fprintf(stderr, "Invalid char: %c\n", *p);
            return NAN;
        }
    }
    while (!isEmptyOp()) {
        char op = popOp();
        double b = popVal(), a = popVal();
        pushVal(apply(op, a, b));
    }
    return popVal();
}

int main() {
    char line[1024];
    printf("Enter expression (empty to quit): ");
    while (fgets(line, sizeof(line), stdin) && line[0] != '\n') {
        line[strcspn(line, "\n")] = 0;
        double ans = evaluate(line);
        if (!isnan(ans)) printf("Result: %.4f\n", ans);
        printf("Enter expression (empty to quit): ");
    }
    return 0;
}

擴展方向

• 支援一元負號：掃描時若 - 前為運算子或開頭，視為一元運算子（優先序最高）。
• 支援函數 (sin, cos, sqrt) 與常數 (PI, E)：擴充 Token 類型與解析器。
• 錯誤恢復：括號不匹配、除零、語法錯誤報行號列位置。

複雜度

時間 O(n)，空間 O(n)，n 為表達式長度。