您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> C 語言問答

中綴表達式轉後綴表達式（逆波蘭表示法）詳細步驟圖解

編輯：C 語言問答

核心算法：Shunting Yard Algorithm (調度場算法)

由 Dijkstra 提出，使用**運算符棧**將中綴轉後綴。核心規則：

操作數直接輸出
左括號入棧
右括號：彈出運算符直到遇到左括號
運算符：若優先級大於棧頂則入棧，否則彈出棧頂輸出直到滿足條件再入棧
掃描結束：彈出剩餘運算符

運算符優先級與結合性

優先級	運算符	結合性
1 (最高)	`()` `[]` `->` `.`	左到右
2	`!` `~` `++` `--` `+`(一元) `-`(一元) `*`(間接) `&`(取址) `sizeof`	右到左
3	`*` `/` `%`	左到右
4	`+` `-`	左到右
...	...	...

題目詳解

(1) `-A+B-C+D` → `A B - C - D +` (即 `A-B+C-D+`)

逐步演示：

步驟	輸入	動作	輸出	運算符棧
1	- (一元負號)	入棧		-
2	A	輸出操作數	A	-
3	+	一元-優先級>+，彈出-輸出，+入棧	A -	+
4	B	輸出操作數	A - B	+
5	-	+與-同級左結合，彈出+輸出，-入棧	A - B +	-
6	C	輸出操作數	A - B + C	-
7	+	-與+同級，彈出-輸出，+入棧	A - B + C -	+
8	D	輸出操作數	A - B + C - D	+
9	結束	彈出剩餘+	A - B + C - D +

(2) `A-B+C` → `A B - C +` (即 `AB-*C+`)

步驟	輸入	動作	輸出	運算符棧
1	A	輸出	A
2	*	入棧	A	*
3	- (一元)	一元-優先級>*，入棧	A	*, -
4	B	輸出	A B	*, -
5	+	彈出一元-輸出，彈出*輸出，+入棧	A B - *	+
6	C	輸出	A B - * C	+
7	結束	彈出+	*A B - C +**

C語言實現：中綴轉後綴

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX 100

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/' || op == '%') return 2;
    if (op == '^') return 3;  // 次方，右結合
    return 0;
}

int is_operator(char c) {
    return c=='+'||c=='-'||c=='*'||c=='/'||c=='%'||c=='^';
}

void infix_to_postfix(const char* infix, char* postfix) {
    char stack[MAX];
    int top = -1;
    int j = 0;
    
    for (int i = 0; infix[i]; i++) {
        char c = infix[i];
        if (isspace(c)) continue;
        
        if (isalnum(c)) {  // 操作數
            postfix[j++] = c;
        } else if (c == '(') {
            stack[++top] = c;
        } else if (c == ')') {
            while (top >= 0 && stack[top] != '(') {
                postfix[j++] = stack[top--];
            }
            if (top >= 0) top--;  // 彈出左括號
        } else if (is_operator(c)) {
            // 處理一元運算符簡化：假設表達式已預處理或用特殊標記
            while (top >= 0 && stack[top] != '(' && 
                   precedence(stack[top]) >= precedence(c)) {
                postfix[j++] = stack[top--];
            }
            stack[++top] = c;
        }
    }
    
    while (top >= 0) {
        postfix[j++] = stack[top--];
    }
    postfix[j] = '\0';
}

int main() {
    char infix[MAX], postfix[MAX];
    printf("輸入中綴表達式: ");
    fgets(infix, MAX, stdin);
    infix[strcspn(infix, "\n")] = '\0';
    
    infix_to_postfix(infix, postfix);
    printf("後綴表達式: %s\n", postfix);
    return 0;
}

後綴表達式求值（驗證轉換正確性）

int eval_postfix(const char* postfix) {
    int stack[MAX];
    int top = -1;
    
    for (int i = 0; postfix[i]; i++) {
        char c = postfix[i];
        if (isdigit(c)) {
            stack[++top] = c - '0';
        } else if (is_operator(c)) {
            int b = stack[top--];
            int a = stack[top--];
            int res = 0;
            switch(c) {
                case '+': res = a + b; break;
                case '-': res = a - b; break;
                case '*': res = a * b; break;
                case '/': res = a / b; break;
            }
            stack[++top] = res;
        }
    }
    return stack[top];
}