---
title: 2B 括弧配對(Medium)
tags: solution
---

# B. 括弧配對(Medium)

- 本題源自於Online Judge(UVa)：[673 - Parentheses Balance](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2412)

## Stack

與上一題的概念很類似，不過會出現`[]`,`()`的兩種情況，因此不太能使用數學加減的方式來判斷是否能互相抵消。

我們的目的是在讓裡面的括號先遇到的就會先被抵銷(被配對)，
而為此，有一個非常好用的資料結構「Stack」就很適合解決此問題。

假設，如果Stack最上面的東東是`[`，遇到`)`就會出錯：`[)`
而如果是遇到`]`則會互相抵消：`[]`

需要特別注意的是在最後輸出的時候記得要判斷Stack是否為空。
(不然像是`([([`之類的例子就會出錯)

#include <iostream>
#include <stack>
using namespace std;

int main() {

    int n = 0;
    cin >> n;
    bool match;
    string str;
    getline(cin, str);

    for ( int i = 0 ; i < n ; i++ ) {
        getline(cin, str);
        stack<char> stk;
        match = true;

        for ( int i = 0 ; i < str.length() && match ; i++ ) {
            if ( str[i] == '(' || str[i] == '[' )
                stk.push( str[i] );
                
            else if ( !stk.empty() && (( str[i] == ')' && stk.top() == '(' ) || 
                                       ( str[i] == ']' && stk.top() == '[' )))
                stk.pop();
                
            else
                match = false;
                
        }
        
        cout << ( ( stk.empty() && match ) ? "Yes\n" : "No\n" );
    }
}