# 課堂練習：括號配對 - 解題報告

## 題目

請撰寫一個程式，輸入一連串括號後，輸出該字串的括號配對是否正確。

正確配對的例子: ( ) ( ) ( ) , ( ( ) ) ( ) , ( ( ) ( ) )
錯誤配對的例子: ) ( ) ( , ( ) ) , ( ( ( ) ( )

### 輸入說明

輸入第一行為正整數 n
接下來是 n 行的`(`或`)`

### 輸出說明

配對正確，輸出 yes，否則輸出 no

### 範例

範例輸入1

6
(
)
(
)
(
)

範例輸出1

yes

範例輸入2

3
(
)
(

範例輸出2

no

範例輸入3

4
(
)
)
(

範例輸出3

no

## 解題思路

在開始解題之前我們要先來了解一下`()`的特性，我們知道：

- 每個`(`都會有一個對應的`)`
- 在`()`內也可以存在`()`，例如：`(())`、`(()())`

接下來我們回到題目要來思考一下，因為**每個`(`都會有一個對應的`)`**，所們只需要把`(`存起下來，然後找到對應的`)`在刪掉，而最後只要我們儲存的容器是空的，且沒有未被配對的`)`，就代表這個括號配對是正確的

以下為實驗例子，以`()(())`做測試

1. 讀入`(`
- 判斷為`(`
- 將其存入容器
2. 讀入`)`
- 判斷為`)`
- 尋找容器內是否有`(`
- 刪除最近存入的`(`，配對成功
3. 讀入`(`
- 判斷為`(`
- 將其存入容器
4. 讀入`(`
- 判斷為`(`
- 將其存入容器
5. 讀入`)`
- 判斷為`)`
- 尋找容器內是否有`(`
- 刪除最近存入的`(`，配對成功
6. 讀入`)`
- 判斷為`)`
- 尋找容器內是否有`(`
- 刪除最近存入的`(`，配對成功
7. 檢查容器是否為空，且沒有`)`需配對
- 輸出結果

在剛才的步驟中我們會發現刪除`(`時，我們需要選擇最近一次存入的來刪除，有此可判斷，我們需要的容器屬於**後進先出**（**LIFO, Last In First Out**）的存取方式，由此可知我們需要的容器是**堆疊**（**Stack**）

綜上所述，我們可以得到以下基礎架構

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

int main()
{
    stack<char> s;
    int n;
    cin >> n;
    bool isValid = true;
    for (int i = 0; i < n; i++){
        char c;
        cin >> c;
        if (c == '(') {
            s.push(c);
        }
        else if (c == ')'){
            s.pop();
        }
    }
    //容器是否判斷為空
    if (!s.empty()){
        isValid = false;
    }
    //根據變數結果來輸出
    if (isValid){
        cout << "yes";
    }
    else{
        cout << "no";
    }

    return 0;
}

但這時會出現一個問題：
**我們該如何判斷有`)`沒配對到呢?**
其實作法很簡單，前面提到過：**每個`(`都會有一個對應的`)`**，所以**只要碰到出現`)`但容器內沒有`(`那就一定是配對失敗**

因此，我們只要在`)`判斷的部分加上容器判斷就可以了

if (s.empty()){
    isValid = false;
    break;
}

>[!Important]`''`和`""`的區別
>在C++這`''`和`""`兩者有明確差別，用途和資料型別也不同
>
>- `""`：雙引號表示字串（string）
>- `''`：表示字元（char）
>
>若兩者混用可能會出問題

## 解答

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

int main()
{
    stack<char> s;
    int n;
    cin >> n;
    bool isValid = true;
    for (int i = 0; i < n; i++){
        char c;
        cin >> c;
        if (c == '(') {
            s.push(c);
        }
        else if (c == ')'){
            if (s.empty()) {
                isValid = false;
                break;
            }
            s.pop();
        }
    }
    if (!s.empty()){
        isValid = false;
    }
    if (isValid){
        cout << "yes";
    }
    else {
        cout << "no";
    }

    return 0;
}

## [回到主頁](https://hackmd.io/@Huanyu763/home)