1353：表達式括号比對(stack)

【題目描述】

假設一個表達式有英文字母（小寫）、運算符（+，—，∗，/）和左右小（圓）括号構成，以“@”作為表達式的結束符。請編寫一個程式檢查表達式中的左右圓括号是否比對，若比對，則傳回“YES”；否則傳回“NO”。表達式長度小于255，左圓括号少于20個。

【輸入】

一行資料，即表達式。

【輸出】

一行，即“YES” 或“NO”。

【輸入樣例】

2*(x+y)/(1-x)@

【輸出樣例】

YES

【提示】

【樣例輸入2】

(25+x)(a(a+b+b)@

【樣例輸出2】

NO

分析

1. 隻處理括号字元，别的字元都不用去處理；左括号直接進棧，遇到右括号：

   如果棧為空，說明沒比對上，直接no,然後return；

   如果棧不空，出棧一次；

2. 如果最後字元串處理完，棧不為空，說明也沒比對上（存在多餘的 ‘(’ ）；

#include <bits/stdc++.h>

using namespace std;

string s;
stack<char> stk;

int main() {
    getline(cin, s);
    //左括号進棧，遇到右括号：出棧一次，如果棧為空，說明沒比對上；
    // 如果最後字元串處理完，棧不為空，說明也沒比對上；
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '@')
            break;
        if (s[i] == '(')
            stk.push(s[i]);
        else if (s[i] == ')') {
            if (stk.size() == 0) {
                cout << "NO";
                return 0;
            }
            stk.pop();
        }
    }
    if (stk.size() == 0)
        cout << "YES";
    else
        cout << "NO";
    return 0;
}