C 語言實現逆波蘭表達式求值器（支持括號、四則運算、階乘）

前言

逆波蘭表示法（後綴表達式）消除了括號與優先級歧義，極適合計算機求值。本文實現一個中綴轉後綴並求值的完整程序，支持 `+ - * /`、括號 `()`、階乘 `!`，採用雙棧法（運算符棧 + 操作數棧）單遍掃描完成。

數據結構設計

#define OPSTACK_LENGTH 50
#define NUMSTACK_LENGTH 100
#define MAX_STRING_LENGTH 100

typedef struct {
    char name;      // 運算符字符
    int priority;   // 優先級
    int opnum;      // 目數：1=一元，2=二元
} OPERATOR;

OPERATOR opStack[OPSTACK_LENGTH];
int opStackTop = -1;
double numStack[NUMSTACK_LENGTH];
int numStackTop = -1;

核心輔助函數

// 運算符優先級
int getPriority(char c) {
    if (c == '(' || c == ')') return 0;
    if (c == '!') return 3;
    if (c == '*' || c == '/') return 2;
    if (c == '+' || c == '-') return 1;
    exit(1);
}

// 運算符目數
int getOpNum(char c) {
    if (c == '+' || c == '-' || c == '*' || c == '/') return 2;
    if (c == '!') return 1;
    if (c == '(' || c == ')') return 0;
    exit(1);
}

// 從字符串解析數字（支持小數），更新索引 i
double getNumFromString(char *s, int *i) {
    char buf[MAX_STRING_LENGTH];
    int j = 0;
    while (*s >= '0' && *s <= '9') buf[j++] = *s++;
    if (*s == '.') {
        buf[j++] = *s++;
        while (*s >= '0' && *s <= '9') buf[j++] = *s++;
    }
    *i += j;
    buf[j] = '\0';
    return atof(buf);
}

棧操作封裝

void pushOperator(OPERATOR op) { opStack[++opStackTop] = op; }
OPERATOR popOperator() { return opStack[opStackTop--]; }
void pushNumber(double v) { numStack[++numStackTop] = v; }
double popNumber() { return numStack[numStackTop--]; }

運算執行

double operate2(OPERATOR op) {
    double b = popNumber(), a = popNumber();
    switch (op.name) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;  // 原代碼有誤 a+b，此處修正
    }
    exit(1);
}

double operate1(OPERATOR op) {
    double a = popNumber();
    if (op.name == '!') {
        double r = 1;
        while (a > 1) r *= a--;
        return r;
    }
    exit(1);
}

double operate(OPERATOR op) {
    return (op.opnum == 1) ? operate1(op) : operate2(op);
}

主解析循環（中綴轉後綴並求值）

int main() {
    char str[MAX_STRING_LENGTH];
    scanf("%s", str);  // 輸入如 "3+4*2/(1-5)!" 以 '=' 結束或直接以 '\0' 結束

    // 初始化運算符棧放入哨兵 '#'
    OPERATOR sentinel = {'#', 0, 0};
    pushOperator(sentinel);

    for (int i = 0; str[i] && str[i] != '='; ) {
        if (str[i] >= '0' && str[i] <= '9') {
            pushNumber(getNumFromString(&str[i], &i));
        } else {
            OPERATOR cur = {str[i], getPriority(str[i]), getOpNum(str[i])};
            OPERATOR top = popOperator();

            if (cur.name == '(') {           // 左括號直接入棧
                pushOperator(top);
                pushOperator(cur);
            } else if (cur.name == ')') {    // 右括號：彈出運算直到遇到 '('
                while (top.name != '(') {
                    pushNumber(operate(top));
                    top = popOperator();
                }
                // '(' 已彈出並丟棄
            } else {                         // 普通運算符
                if (top.name != '#' && cur.priority <= top.priority) {
                    pushNumber(operate(top));  // 棧頂優先級 >= 當前，先算棧頂
                } else {
                    pushOperator(top);         // 否則棧頂壓回
                }
                pushOperator(cur);             // 當前入棧
            }
            i++;
        }
    }

    // 清空剩餘運算符
    OPERATOR top;
    while ((top = popOperator()).name != '#')
        pushNumber(operate(top));

    printf("%f\n", popNumber());
    return 0;
}

算法流程圖解

1. 掃描到操作數 → 直接壓入數值棧。
2. 掃描到運算符 → 彈出棧頂運算符比較優先級：
   • `(` 直接入棧（最低優先級，但不參與比較）。
   • `)` 觸發連續彈出計算，直到遇到 `(`。
   • 普通運算符：若棧頂優先級 ≥ 當前，先計算棧頂；否則棧頂壓回。然後當前入棧。
3. 掃描結束 → 依次彈出剩餘運算符計算。
4. 數值棧剩餘唯一值即結果。

測試用例

擴展建議

• 支持負數：解析數字時識別前導 `-` 為一元負號（優先級高於乘除）。
• 支持變量/函數：引入符號表，`sin`、`cos` 等視為一元運算符。
• 錯誤處理：除零、棧溢出、括號不匹配、非法字符均應拋出異常而非 `exit(1)`。
• 輸出後綴表達式：在 `pushNumber` 時同時輸出到字符串，得到標準 RPN 序列。