ZeroJudge K621: [紅]括號匹配問題

假設表達式中允許包含圓括號和方括號兩種括號，其嵌套的順序隨意。

例如：( [ ] ( ) ) 以及 [ ( [ ] [ ] ) ] 都是正確的匹配，而 [ ( ] ) 以及 ( ( ) ) ) 都是錯誤的匹配。

本題的任務是檢驗一個給定表達式中的括號是否正確匹配。

範例測資

範例輸入範例輸出
輸入一行字串 S，只有圓括號和方括號，S 的字元不多於500。若表達式中的括號為正確匹配，則輸出「Right」；
否則就輸出「Wrong」。
[([][])]Right
[(])Wrong

解題思路

跑字串的 For迴圈，如果是左括號的話將這個字元存放到一個 Vector 中，如果是右括號的話判斷目前Vector最後一個字元是否跟這個右括號匹配，如果匹配的話就將Vector最後一個資料Pop_Back，如果不匹配的話直接輸出 Wrong 並將迴圈Break掉。如果 For迴圈 跑完 Vector 中還有資料的話也是Wrong。

範例程式碼－ZeroJudge K621: [紅]括號匹配問題

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

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    string str;
    cin >> str;
    vector<char>v;
    bool ok = true;
    for (int i = 0; i<str.length(); i++)
    {
        if (str[i] == '(' || str[i] == '[')
        {
            v.push_back(str[i]);
        }
        else
        {
            if (str[i] == ')')
            {
                if (v.size() > 0 && v[int(v.size()-1)] == '(') v.pop_back();
                else
                {
                    ok = false;
                    cout << "Wrong\n";
                    break;
                }
            }
            else
            {
                if (v.size() > 0 && v[int(v.size()-1)] == '[') v.pop_back();
                else
                {
                    ok = false;
                    cout << "Wrong\n";
                    break;
                }
            }
        }
    }
    if (ok && v.size() != 0)
    {
        ok = false;
        cout << "Wrong\n";
    }
    if (ok) cout << "Right\n";
}

//ZeroJudge K621
//Dr. SeanXD
標籤

相關文章

發佈留言