BRACKETS 2(対にならない括弧)
3141 ワード
(ソース)https://algospot.com/judge/problem/read/BRACKETS2
左かっこと右かっこ
この問題は,与えられた条件に基づいて左かっこと右かっこがペアであるか否かを判断する問題である.かっこパターンを直接描くと、判断の基準が最終的に閉じたかっこになることがわかりやすい.
かっこパターンを直接いくつか描くと、問題条件に合ったカッコパターンが発見され、どのパターンでも最初の右カッコの真ん前に対をなす左カッコが必要になります.また,パターンから対称の括弧を削除し,次の最も速い閉じた括弧を再び見ると,上記の事実も同様に成り立っていることが分かる.
つまり、最速の括弧を基準に、上位の括弧が正しいか正しいかを判断し、すべてが正しいことを確認すればよい.
前からかっこを1つずつ保存する場合、最初に表示される閉じたかっこは、削除するために最後に保存された左かっことペアになって実装されます.したがって、実装に使用する特定の資料構造を選択しなければならない場合、スタックの使用が最も便利に見えます.ベクトルでも十分に実現できるが,スタックデータ構造の利用を明眼的に誘導する問題であるためスタックで実現した.
コード#コード#
本で実現したコードから見ると,オープンカッコとクローズカッコの文字リストはそれぞれ2つの配列に格納され,互いにペアを組んだカッコは各配列の同じインデックスを用いて論理対を形成している.本当の本の体現は私の体現に比べて、私の体現はとても冷たいように見えます.このようなコードの編成方法を熟知しなければならない.
左かっこと右かっこ
この問題は,与えられた条件に基づいて左かっこと右かっこがペアであるか否かを判断する問題である.かっこパターンを直接描くと、判断の基準が最終的に閉じたかっこになることがわかりやすい.
かっこパターンを直接いくつか描くと、問題条件に合ったカッコパターンが発見され、どのパターンでも最初の右カッコの真ん前に対をなす左カッコが必要になります.また,パターンから対称の括弧を削除し,次の最も速い閉じた括弧を再び見ると,上記の事実も同様に成り立っていることが分かる.
つまり、最速の括弧を基準に、上位の括弧が正しいか正しいかを判断し、すべてが正しいことを確認すればよい.
前からかっこを1つずつ保存する場合、最初に表示される閉じたかっこは、削除するために最後に保存された左かっことペアになって実装されます.したがって、実装に使用する特定の資料構造を選択しなければならない場合、スタックの使用が最も便利に見えます.ベクトルでも十分に実現できるが,スタックデータ構造の利用を明眼的に誘導する問題であるためスタックで実現した.
コード#コード#
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
using namespace std;
stack<char> brackets2(string& pattern) {
stack<char> s;
for (int i = 0; i < pattern.size(); i++) {
if (pattern[i] == '(' || pattern[i] == '{' || pattern[i] == '[') s.push(pattern[i]);
else {
if (pattern[i] == ')') {
if (s.empty() || s.top() != '(') {
s.push('N');
break;
}
else {
s.pop();
continue;
}
}
if (pattern[i] == '}') {
if (s.empty() || s.top() != '{') {
s.push('N');
}
else {
s.pop();
continue;
}
}
if (pattern[i] == ']') {
if (s.empty() || s.top() != '[') {
s.push('N');
}
else {
s.pop();
continue;
}
}
}
}
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int testcase;
cin >> testcase;
while (testcase--) {
string pattern;
cin >> pattern;
stack<char> ret = brackets2(pattern);
if (ret.size() != 0) cout << "NO" << '\n';
else cout << "YES" << '\n';
}
return 0;
}
覚えたいこと本で実現したコードから見ると,オープンカッコとクローズカッコの文字リストはそれぞれ2つの配列に格納され,互いにペアを組んだカッコは各配列の同じインデックスを用いて論理対を形成している.本当の本の体現は私の体現に比べて、私の体現はとても冷たいように見えます.このようなコードの編成方法を熟知しなければならない.
Reference
この問題について(BRACKETS 2(対にならない括弧)), 我々は、より多くの情報をここで見つけました https://velog.io/@dlsghl92/BRACKETS2짝이맞지않는괄호テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol