C 語言鏈棧算術表達式求值：另一份完整實現 (嚴蔚敏版)

代碼來源

基於《數據結構》(嚴蔚敏版) 運算符優先算法，純 C 實現，無 STL 依賴。

完整代碼 (已修正可編譯)

#include 
#include 
#include 
#include 
#include 

#define TRUE 1
#define FALSE 0
#define OPSETSIZE 7
typedef int Status;

char OPSET[OPSETSIZE] = {'+', '-', '*', '/', '(', ')', '#'};
char PRIOR[OPSETSIZE][OPSETSIZE] = {
    {'>','>','<','<','<','>','>'}, // +
    {'>','>','<','<','<','>','>'}, // -
    {'>','>','>','>','<','>','>'}, // *
    {'>','>','>','>','<','>','>'}, // /
    {'<','<','<','<','<','=',' '}, // (
    {'>','>','>','>',' ','>','>'}, // )
    {'<','<','<','<','<',' ','='}, // #
};

typedef struct SC { char c; struct SC *next; } *StackChar;
typedef struct SF { double f; struct SF *next; } *StackFloat;

StackChar pushSC(StackChar s, char c) {
    StackChar p = malloc(sizeof(*p)); p->c = c; p->next = s; return p;
}
StackChar popSC(StackChar s) { StackChar q = s; s = s->next; free(q); return s; }
StackFloat pushSF(StackFloat s, double f) {
    StackFloat p = malloc(sizeof(*p)); p->f = f; p->next = s; return p;
}
StackFloat popSF(StackFloat s) { StackFloat q = s; s = s->next; free(q); return s; }

int inOpSet(char ch) {
    for (int i = 0; i < OPSETSIZE; i++) if (OPSET[i] == ch) return TRUE;
    return FALSE;
}
int opIndex(char op) {
    for (int i = 0; i < OPSETSIZE; i++) if (OPSET[i] == op) return i;
    return -1;
}
char precede(char a, char b) {
    return PRIOR[opIndex(a)][opIndex(b)];
}
double operate(double a, char op, double b) {
    switch(op) {
        case '+': return a+b;
        case '-': return a-b;
        case '*': return a*b;
        case '/': return b==0 ? NAN : a/b;
    }
    return NAN;
}

double evaluateExpression(char *expr) {
    StackChar optr = NULL;
    StackFloat opnd = NULL;
    optr = pushSC(optr, '#');
    char *p = expr;
    char numBuf[32];
    int bufLen = 0;

    while (*p != '#' || ((StackChar)optr)->c != '#') {
        if (isdigit(*p) || *p == '.') {
            numBuf[bufLen++] = *p++;
        } else {
            if (bufLen > 0) {
                numBuf[bufLen] = '\0';
                opnd = pushSF(opnd, atof(numBuf));
                bufLen = 0;
            }
            if (*p == '\0') break;
            if (!inOpSet(*p)) { p++; continue; }
            switch (precede(((StackChar)optr)->c, *p)) {
                case '<': optr = pushSC(optr, *p); p++; break;
                case '=': optr = popSC(optr); p++; break;
                case '>': {
                    char op = ((StackChar)optr)->c;
                    optr = popSC(optr);
                    double b = ((StackFloat)opnd)->f; opnd = popSF(opnd);
                    double a = ((StackFloat)opnd)->f; opnd = popSF(opnd);
                    opnd = pushSF(opnd, operate(a, op, b));
                    break;
                }
            }
        }
    }
    double result = ((StackFloat)opnd)->f;
    // 釋放剩餘棧內存 (略)
    return result;
}

int main() {
    char expr[256];
    printf("輸入表達式 (以 # 結束): ");
    fgets(expr, sizeof(expr), stdin);
    expr[strcspn(expr, "\n")] = '#';
    printf("結果: %g\n", evaluateExpression(expr));
    return 0;
}

與上一版本 (ID 28850) 差異對比

編譯運行驗證

$ gcc -std=c99 -o calc calc.c -lm
$ ./calc
輸入表達式 (以 # 結束): 3+4*2/(1-5)#
結果: 1

教學重點

1. 兩棧法：OPTR 存運算符，OPND 存運算數。
2. 優先級表驅動：移進 (<), 歸約 (>), 脫括號 (=)。
3. 鏈棧操作：push/pop 封裝，主邏輯清晰。
4. 字符流掃描：指針遍歷 + 數字緩衝區。

常見錯誤調試

• 除零未檢查 → operate 中返回 NAN 或設置錯誤碼。
• 表達式非法字符 → inOpSet 過濾。
• 括號不匹配 → 循環終止條件檢測 optr->c == '#' 但 *p != '#'。
• 內存洩漏 → 程序結束前遍歷釋放兩棧所有節點。

總結

這是經典教科書級實現，適合**數據結構課程作業**、**嵌入式無 STL 環境**、**面試手寫算法**。生產環境請用成熟庫 (tinyexpr, muParser)。