使用堆疊實現表達式括號匹配檢查

題目描述

給定一個由英文小寫字母、運算符（+、-、*、/）以及左右圓括號組成的表達式，並以「@」作為結束符號。請編寫程序檢查表達式中的左右括號是否正確匹配。若匹配則輸出「YES」，否則輸出「NO」。表達式長度小於 255，左括號少於 20 個。

輸入輸出格式

輸入： 一行字串，即帶有結束符 @ 的表達式。

輸出： 單行「YES」或「NO」。

範例

輸入範例 1： 2*(x+y)/(1-x)@ → 輸出： YES

輸入範例 2： (25+x)*(a*(a+b+b)@ → 輸出： NO

解題思路

採用計數器模擬堆疊行為：掃描字串，遇到左括號「(」計數器加 1，遇到右括號「)」計數器減 1。若過程中計數器變為負數，表示右括號多於左括號，直接判定不匹配；掃描結束後，計數器為 0 則匹配，否則不匹配。

參考代碼 (C)

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

char a[260];

int main() {
    int i = 0, k = 0, len;
    gets(a);
    len = strlen(a) - 1;  // 排除結束符 @
    for (i = 0; i <= len; i++) {
        if (a[i] == '(') k++;
        if (a[i] == ')') k--;
        if (k < 0) break;  // 提前檢測右括號過多
    }
    if (k == 0) printf("YES");
    else printf("NO");
    return 0;
}

該解法時間複雜度 O(n)，空間複雜度 O(1)，完美符合題目限制。