假設表達式中允許包含圓括號和方括號兩種括號,其嵌套的順序隨意。
例如:( [ ] ( ) ) 以及 [ ( [ ] [ ] ) ] 都是正確的匹配,而 [ ( ] ) 以及 ( ( ) ) ) 都是錯誤的匹配。
本題的任務是檢驗一個給定表達式中的括號是否正確匹配。
範例測資
範例輸入 | 範例輸出 |
---|---|
輸入一行字串 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