PAT 06-1 簡單計算器：左到右等優先級四則運算解題詳解

題目需求分析

• 只處理 + - * / 四種運算符
• 運算數與結果均為整數
• 優先級相同，從左到右順序計算（無運算符優先級）
• 輸入以 = 結束，無空格
• 除數為 0 或非法運算符輸出 ERROR

樣例

輸入：1+2*10-10/2=
按左到右計算：((1+2)*10-10)/2 = (3*10-10)/2 = (30-10)/2 = 20/2 = 10
輸出：10

算法設計

核心思想：流式處理

讀取首個操作數 → 循環讀取 <運算符, 操作數> 對 → 即時計算 → 遇 = 結束。

關鍵步驟

1. scanf("%d", &n) 讀首個數
2. while ((ch = getchar()) != '=') 讀運算符
3. scanf("%d", &tmp) 讀下一操作數
4. 檢查除零：if (tmp == 0 && ch == '/')
5. switch(ch) 執行對應運算更新 n
6. 非法運算符標記錯誤
7. 循環結束後根據標記輸出結果或 ERROR

標準實現代碼

#include <stdio.h>
#include <stdbool.h>

int main(void) {
    int n, tmp;
    char ch;
    bool ok = true;

    if (scanf("%d", &n) != 1) return 0;  // 無輸入直接退出

    while ((ch = getchar()) != '=') {
        if (scanf("%d", &tmp) != 1) { ok = false; break; }

        if (tmp == 0 && ch == '/') {
            ok = false;
        } else {
            switch (ch) {
                case '+': n += tmp; break;
                case '-': n -= tmp; break;
                case '*': n *= tmp; break;
                case '/': n /= tmp; break;  // 整數除法，C99 規定向零截斷
                default: ok = false;        // 非法運算符
            }
        }
        if (!ok) break;
    }

    if (ok) printf("%d\n", n);
    else    printf("ERROR\n");

    return 0;
}

關鍵細節與易錯點

1. 輸入流處理

• scanf("%d") 會自動跳過空白字符（空格、換行、制表符）
• getchar() 讀取單字符，不跳過空白，適合讀運算符
• 組合使用完美匹配「無空格」輸入格式

2. 整數除法行為

C99 標準規定整數除法向零截斷（5/2=2，-5/2=-2）。題目僅涉及正整數，無負數歧義。

3. 溢出風險

題目未給數據範圍，實際比賽中建議用 long long 或檢查溢出。若確定數據較小，int 足夠。

4. 變量初始化

ok = true 必須在循環前初始化，避免未定義行為。

測試用例

擴展思考

若需支持標準運算符優先級（乘除先於加減），需引入雙棧法（操作數棧 + 運算符棧）或遞歸下降解析器，這是編譯原理中表達式求值的經典模型。

本題通過限制優先級相同，將難度控制在「流式單遍歷」層面，考察基本輸入處理與分支邏輯能力。