C 語言鏈棧實現算術表達式求值：運算符優先級法完整代碼

算法原理：運算符優先級 (Operator Precedence) 分析法

維護兩棧：運算符棧 (OPTR)、運算數棧 (OPND)。掃描表達式字符：

• 操作數 → 進 OPND
• 運算符 → 與 OPTR 栈頂比較優先級：
  < 進棧 | = 脫括號 | > 執行運算、結果入 OPND

完整可運行代碼 (C99 標準)

#include 
#include 
#include 
#include 
#include 

#define OPSETSIZE 7
typedef int Status;

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

// 優先級表: 行=棧頂, 列=當前
char PRIOR[OPSETSIZE][OPSETSIZE] = {
    /* +  -  *  /  (  )  # */
    {'>','>','<','<','<','>','>'}, // +
    {'>','>','<','<','<','>','>'}, // -
    {'>','>','>','>','<','>','>'}, // *
    {'>','>','>','>','<','>','>'}, // /
    {'<','<','<','<','<','=',' '}, // (
    {'>','>','>','>',' ','>','>'}, // )
    {'<','<','<','<','<',' ','='}, // #
};

typedef struct SNode { char data; struct SNode *next; } *Stack;
typedef struct FNode { double data; struct FNode *next; } *FStack;

Stack pushChar(Stack s, char c) {
    Stack n = malloc(sizeof(*n)); n->data = c; n->next = s; return n;
}
Stack popChar(Stack s) { Stack t = s; s = s->next; free(t); return s; }
FStack pushDouble(FStack s, double d) {
    FStack n = malloc(sizeof(*n)); n->data = d; n->next = s; return n;
}
FStack popDouble(FStack s) { FStack t = s; s = s->next; free(t); return s; }

int getOpIndex(char op) {
    for (int i = 0; i < OPSETSIZE; i++) if (OPSET[i] == op) return i;
    return -1;
}
char precede(char top, char cur) {
    return PRIOR[getOpIndex(top)][getOpIndex(cur)];
}
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 evaluate(const char *expr) {
    Stack optr = NULL;
    FStack opnd = NULL;
    optr = pushChar(optr, '#');
    char *p = (char*)expr;
    char numBuf[32];
    int bufLen = 0;

    while (*p != '#' || ((Stack)optr)->data != '#') {
        if (isdigit(*p) || *p == '.') {
            numBuf[bufLen++] = *p++;
        } else {
            if (bufLen > 0) {
                numBuf[bufLen] = '\0';
                opnd = pushDouble(opnd, atof(numBuf));
                bufLen = 0;
            }
            if (*p == '\0') break;
            char cur = *p;
            if (getOpIndex(cur) == -1) { p++; continue; } // 忽略空格等
            switch (precede(((Stack)optr)->data, cur)) {
                case '<': optr = pushChar(optr, cur); p++; break;
                case '=': optr = popChar(optr); p++; break; // 脫括號
                case '>': {
                    char op = ((Stack)optr)->data;
                    optr = popChar(optr);
                    double b = ((FStack)opnd)->data; opnd = popDouble(opnd);
                    double a = ((FStack)opnd)->data; opnd = popDouble(opnd);
                    opnd = pushDouble(opnd, operate(a, op, b));
                    break;
                }
            }
        }
    }
    double result = ((FStack)opnd)->data;
    // 清理棧內存 (略)
    return result;
}

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

關鍵數據結構

優先級表設計說明

• + - 同級，最低 (除括號外)
• * / 同級，高於 + -
• ( 在棧內優先級最低 (遇任何運算符進棧)，但遇 ) 時相等 (脫括號)
• # 為最低界限符，棧底與表達式尾部

測試用例

輸入: 3+5*(2-1)#
輸出: 8

輸入: (12+34)*5/2#
輸出: 115

輸入: 2^3^2#  (需擴展 ^ 右結合)
輸出: 512

擴展方向

1. 支持一元運算符 (負號、正弦餘弦)
2. 支持變量查表 (符號表)
3. 生成中間代碼 / AST 而非直接求值
4. 錯誤恢復與語法錯誤定位

總結

鏈棧實現表達式求值核心在於 **優先級表驅動的移進/歸約**。代碼無 STL 依賴，純 C 實現，適合嵌入式/教學環境。生產環境建議成熟表達式解析庫 (muParser, tinyexpr)。