C 語言實現前綴表達式求值：棧式算法完整解析

題目回顧

輸入一行不超過 30 字符的前綴表達式（運算符與運算元以空格分隔），如 + + 2 * 3 - 7 4 / 8 4，要求計算結果，保留 1 位小數；異常情況輸出 ERROR。

核心思路：從右向左掃描 + 棧

1. 將表達式按空格分割為 token 數組。
2. 從**最右端**開始遍歷：
   • 遇到**運算元**（數字），轉 double 入棧。
   • 遇到**運算符**（+ - * /），彈出棧頂兩個元素 op1, op2（注意順序），計算 op1 運算符 op2，結果入棧。
3. 遍歷結束，棧頂即為最終結果。

關鍵細節

• 除零檢查：執行 / 前判斷 op2 == 0，報錯。
• 操作數合法性：strtod 解析失敗視為錯誤。
• 棧深度：表達式長度 ≤ 30，靜態數組 double st[30] 足夠。
• 輸出格式：printf("%.1f\n", result)；錯誤時 puts("ERROR")。

參考代碼框架

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

#define MAX_TOKENS 30

int main() {
    char line[200];
    if (!fgets(line, sizeof(line), stdin)) return 0;
    line[strcspn(line, "\n")] = 0; // 去換行

    char *tokens[MAX_TOKENS];
    int n = 0;
    for (char *p = strtok(line, " "); p; p = strtok(NULL, " "))
        tokens[n++] = p;

    double st[MAX_TOKENS];
    int top = -1;
    int error = 0;

    for (int i = n - 1; i >= 0; i--) {
        char *tk = tokens[i];
        if (isdigit(tk[0]) || (tk[0]=='-' && isdigit(tk[1]))) {
            char *end;
            double val = strtod(tk, &end);
            if (*end != '\0') { error = 1; break; }
            st[++top] = val;
        } else if (strlen(tk) == 1 && strchr("+-*/", tk[0])) {
            if (top < 1) { error = 1; break; }
            double b = st[top--], a = st[top--];
            switch (tk[0]) {
                case '+': st[++top] = a + b; break;
                case '-': st[++top] = a - b; break;
                case '*': st[++top] = a * b; break;
                case '/': 
                    if (b == 0) { error = 1; }
                    else st[++top] = a / b;
                    break;
            }
        } else { error = 1; break; }
        if (error) break;
    }

    if (error || top != 0) puts("ERROR");
    else printf("%.1f\n", st[0]);
    return 0;
}

測試樣例

掌握「右掃左算、棧存中間結果」模板，前綴/後綴表達式求值題迎刃而解。