C 語言資料結構實戰：棧實現四則運算表達式求值 (中綴轉後綴 + 後綴求值)

編輯：關於C語言

利用棧的「先進後出」特性，可優雅解決算術表達式的括號匹配、運算符優先級與結合性問題。本文完整實現：中綴表達式 → 後綴表達式 (逆波蘭表示法) → 棧式求值，支援多位數、小數、括號巢狀與四則運算，是簡易計算器核心邏輯的經典教學案例。

一、核心資料結構


#define MAXSIZE 100
typedef float DataType;      // 操作數類型

// 操作數棧 (浮點數)
typedef struct {
    DataType data[MAXSIZE];
    int top;                 // 棧頂索引，-1 為空
} SeqStackNum;

// 運算符棧 (字元)
typedef struct {
    char data[MAXSIZE];
    int top;
} SeqStackOp;

二、輔助判斷函數


// 是否為運算符
int isOperator(char op) {
    return (op == '+' || op == '-' || op == '*' || op == '/');
}

// 運算符優先級 (數值越大優先級越高)
int precedence(char op) {
    switch (op) {
        case '#': return -1;  // 棧底哨兵，最低
        case '(': return 0;   // 左括號入棧最低，遇右括號觸發彈出
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        default: return -1;
    }
}

三、中綴轉後綴核心演算法

採用 Dijkstra Shunting-yard 演算法 精簡版：


void infixToPostfix(char *infix, char *postfix, SeqStackOp *opStack, SeqStackNum *numStack) {
    int i = 0, j = 0;
    pushOp(opStack, '#');  // 哨兵入棧

    while (infix[i] != '#') {  // 輸入以 # 結束
        char c = infix[i];

        // 1. 數字/小數點 → 直接輸出
        if ((c >= '0' && c <= '9') || c == '.') {
            postfix[j++] = c;
        }
        // 2. 左括號 → 直接入運算符棧
        else if (c == '(') {
            pushOp(opStack, c);
        }
        // 3. 右括號 → 彈出運算符至輸出，直到遇到左括號
        else if (c == ')') {
            while (opStack->data[opStack->top] != '(') {
                postfix[j++] = popOp(opStack);
            }
            popOp(opStack); // 彈出左括號 '('
        }
        // 4. 運算符
        else if (isOperator(c)) {
            postfix[j++] = ' ';  // 輸出空格分隔操作數
            // 棧頂運算符優先級 >= 當前運算符，先彈出
            while (precedence(opStack->data[opStack->top]) >= precedence(c)) {
                postfix[j++] = popOp(opStack);
            }
            pushOp(opStack, c); // 當前運算符入棧
        }
        i++;
    }

    // 5. 輸入結束，彈出剩餘運算符
    while (opStack->top > 0) { // 忽略哨兵 '#'
        postfix[j++] = popOp(opStack);
    }
    postfix[j] = '\0';

    // 6. 直接調用後綴求值
    evaluatePostfix(postfix, numStack);
}

關鍵細節

空格分隔符：運算符輸出前加空格 (`postfix[j++] = ' ';`)，區分多位數 (如 `12 3 +` vs `1 23 +`)。
哨兵 `#`**：簡化棧空判斷與循環終止條件。
左括號優先級 0**：入棧時不觸發彈出；遇右括號時作為邊界彈出。

四、後綴表達式求值


// 從後綴串讀取下一個數字 (支援整數/小數)
float readNumber(char *postfix, int *index) {
    float val = 0.0;
    int decimalPlaces = 0;
    bool isDecimal = false;

    // 整數部分
    while (postfix[*index] >= '0' && postfix[*index] <= '9') {
        val = val * 10 + (postfix[*index] - '0');
        (*index)++;
    }

    // 小數部分
    if (postfix[*index] == '.') {
        isDecimal = true;
        (*index)++;
        while (postfix[*index] >= '0' && postfix[*index] <= '9') {
            val = val * 10 + (postfix[*index] - '0');
            decimalPlaces++;
            (*index)++;
        }
    }

    while (decimalPlaces-- > 0) val /= 10.0;
    return val;
}

// 後綴求值主循環
void evaluatePostfix(char *postfix, SeqStackNum *numStack) {
    int i = 0;
    while (postfix[i] != '\0') {
        if (postfix[i] >= '0' && postfix[i] <= '9') {
            pushNum(numStack, readNumber(postfix, &i));
        }
        else if (postfix[i] == ' ') { // 跳過分隔符
            i++;
        }
        else { // 運算符
            float b = popNum(numStack); // 右操作數
            float a = popNum(numStack); // 左操作數
            float result = 0;

            switch (postfix[i]) {
                case '+': result = a + b; break;
                case '-': result = a - b; break;
                case '*': result = a * b; break;
                case '/': result = a / b; break; // 注意除零
            }
            pushNum(numStack, result);
            i++;
        }
    }
    // 最終結果在棧頂
    printf("Result: %.2f\n", numStack->data[numStack->top]);
}

五、完整測試主程式


int main() {
    SeqStackOp opStack = { .top = -1 };
    SeqStackNum numStack = { .top = -1 };
    
    // 輸入表達式以 # 結束，空格非必要 (演算法自動插入分隔)
    char infix[] = "3.5*(12-4)/2+10#"; 
    char postfix[MAXSIZE * 2] = {0}; // 後綴可能更長

    printf("Infix: %s\n", infix);
    infixToPostfix(infix, postfix, &opStack, &numStack);
    printf("Postfix: %s\n", postfix);
    // 輸出: 3.5 12 4 - * 2 / 10 + 
    // Result: 24.00

    return 0;
}