運算式求值實作：中序轉後序（逆波蘭表示法）與堆疊計算完整教學

編輯：關於C語言

前言

本文實作運算式的後綴表示（逆波蘭表示法，RPN）轉換與求值，採用堆疊資料結構處理運算子優先序與括號巢狀。程式碼以 C 語言撰寫，包含詳細註解。

資料結構定義

typedef int ElemType;  // 為避免 char 運算隱性提升溢位，使用 int
#define MAXNUM 16

struct Stack {
    ElemType data[MAXNUM];
    int top;
};

堆疊基本操作

初始化

void StackInit(struct Stack *s)
{
    for (int i = 0; i < MAXNUM; i++)
        s->data[i] = 0;
    s->top = 0;  // 堆疊底部從索引 0 開始
}

推入

void StackPush(struct Stack *s, ElemType c)
{
    if (MAXNUM == s->top) {
        printf("堆疊已滿\n");
        return;
    }
    s->data[s->top++] = c;
}

彈出

ElemType StackPop(struct Stack *s)
{
    if (0 == s->top) {
        printf("堆疊為空\n");
        return 0;  // 實際應用應處理錯誤
    }
    return s->data[--s->top];
}

中序轉後序演算法

使用兩個堆疊：ch_stack 儲存輸出運算元與運算子，op_stack 暫存運算子。掃描輸入字串，依字元類型處理：

運算子 + - * /：依優先序彈出 op_stack 中優先序較高或相等的運算子至 ch_stack，再推入當前運算子。
左括號 (：直接推入 op_stack。
右括號 )：彈出 op_stack 至遇到左括號，輸出中間運算子至 ch_stack，丟棄左右括號。
數字 0-9：處理多位數，連續數字合併為單一運算元推入 ch_stack。

int ChangeToPostfix(char *str)
{
    int i = 0, flag = 0;  // flag 標記連續數字
    int c, ch;
    struct Stack ch_stack, op_stack;
    StackInit(&ch_stack);
    StackInit(&op_stack);

    while ('\0' != (c = *(str + i))) {
        if (('*' == c) || ('/' == c) || ('(' == c)) {
            flag = 0;
            StackPush(&op_stack, c);
        }
        else if (')' == c) {
            flag = 0;
            while ('(' != (c = StackPop(&op_stack))) {
                StackPush(&ch_stack, c);
            }
            if (0 == op_stack.top) {
                printf("找不到配對的左括號\n");
                return -1;
            }
        }
        else if (('+' == c) || ('-' == c)) {
            flag = 0;
            if (0 != op_stack.top) {
                while ('(' != (ch = StackPop(&op_stack))) {
                    StackPush(&ch_stack, ch);
                    if (0 == op_stack.top) break;
                }
            }
            StackPush(&op_stack, c);
        }
        else if ((c >= '0') && (c <= '9')) {
            if (0 == flag) {
                StackPush(&ch_stack, (c - '0'));
                flag = 1;
            }
            else {
                StackPush(&ch_stack, 10 * StackPop(&ch_stack) + (c - '0'));
            }
        }
        i++;
    }

    while (0 != op_stack.top)
        StackPush(&ch_stack, StackPop(&op_stack));

    // 此處可呼叫 PostfixEvaluation(&ch_stack) 進行計算
    // 為示範輸出後序表示式：
    for (i = 0; i < ch_stack.top; i++) {
        if ('+' == ch_stack.data[i]) printf("+ ");
        else if ('-' == ch_stack.data[i]) printf("- ");
        else if ('*' == ch_stack.data[i]) printf("* ");
        else if ('/' == ch_stack.data[i]) printf("/ ");
        else printf("%d ", ch_stack.data[i]);
    }
    printf("\n");
    return 0;
}

主程式測試

int main(void)
{
    char str[] = "12+34*435-5/1";
    printf("預期後序：12 34 435 * + 5 1 / - [結果=8]\n");
    if (-1 == ChangeToPostfix(str)) {
        printf("轉換錯誤\n");
        return 1;
    }
    return 0;
}