LeetCode(20) Valid Parentheses
タイトルは以下の通り
Given a string containing justthe characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()"and "()[]{}"are all valid but "(]"and "([)]"are not.
この問題は簡単で、stackの基本的な操作さえできれば完成できます.テーマの一番肝心な言葉はjustだと思いますが、入力した文字は6つしかないことを教えてあげます.justという言葉がなければ、頭と尾のスペースを落とさなければならないのか、不正な文字は問題のニーズに応じて処理しなければならないのか、などを考えなければなりません.まず以下の例を見て、validかどうかを判断します.
(((())) TRUE [][][] TRUE ((([]))) TRUE ((([]{}))) TRUE ([{}]) TRUE ([{[][]}]) TRUE ]}]) FALSE (((( FALSE )()()( FALSE
以下では(,[,{左かっこ,把)],}を右かっこと呼ぶ.
このいくつかの例から見ると、左かっこが1回現れた場合、右かっこもペアで1回現れなければならない.実はそう言うのはまだ正確ではありません.そう言えばvalidの必要条件で、まだ十分な条件ではありません.例えば、上の例の最後の例を見ると、わかります.左右のかっこは1対1でペアリングできるだけでなく、左から右の順番を満たす必要があります.
入力文字がこの条件を満たすかどうかを検出するには、非常に適切なデータ構造がstackであり、後進先出の特徴が検出のニーズを満たす.検出の際、1文字ずつチェックし、左かっこであればスタックに入る、右かっこであれば現在のスタックトップ記号と右かっこであればスタックトップをポップアップして次の検出を行い、上記の2つの状況を満たさなければ、不正な文字が検出されたことを説明し、falseに戻る.
では、入力文字列(((([]))を例にとります.
ステップ1～3サイクル目、stackはスタックの3つの左カッコ(現在のスタックの上部は左カッコ)に入ります.
4ステップ目のループでは、stackはスタックの左方括弧[、現在のスタックの上部は左方括弧、スタック内の要素は1つの左方括弧に入ります.
5ステップ目のループでは、右方のカッコが見つかり、ちょうど現在のスタックの上部の左方のカッコ[左右のペアを満たすため、スタックを弾き、現在のスタックの上部は左のカッコに戻り、スタックの要素は3つの左のカッコになります.
6ステップ目のループでは、右カッコが発見され、現在のスタックトップの左カッコ(左右のペアを満たすため、スタックを弾き、現在のスタックトップは依然として左カッコを維持し、スタック内の要素は2つの左カッコである.
7ステップ目のループでは、右カッコが発見され、現在のスタックトップの左カッコ(左右のペアを満たすため、スタックを弾き、現在のスタックトップは依然として左カッコを維持し、スタック内の要素は1つの左カッコである.
8ステップ目のループでは、右カッコが見つかり、現在のスタックの上部の左カッコ(左右のペアを満たすため、スタックを弾き、スタック内の要素は0です.
入力文字列のループが完了すると、チェックstackが空になるのでtrueを返します.
コードは次のとおりです.
Given a string containing justthe characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()"and "()[]{}"are all valid but "(]"and "([)]"are not.
この問題は簡単で、stackの基本的な操作さえできれば完成できます.テーマの一番肝心な言葉はjustだと思いますが、入力した文字は6つしかないことを教えてあげます.justという言葉がなければ、頭と尾のスペースを落とさなければならないのか、不正な文字は問題のニーズに応じて処理しなければならないのか、などを考えなければなりません.まず以下の例を見て、validかどうかを判断します.
(((())) TRUE [][][] TRUE ((([]))) TRUE ((([]{}))) TRUE ([{}]) TRUE ([{[][]}]) TRUE ]}]) FALSE (((( FALSE )()()( FALSE
以下では(,[,{左かっこ,把)],}を右かっこと呼ぶ.
このいくつかの例から見ると、左かっこが1回現れた場合、右かっこもペアで1回現れなければならない.実はそう言うのはまだ正確ではありません.そう言えばvalidの必要条件で、まだ十分な条件ではありません.例えば、上の例の最後の例を見ると、わかります.左右のかっこは1対1でペアリングできるだけでなく、左から右の順番を満たす必要があります.
入力文字がこの条件を満たすかどうかを検出するには、非常に適切なデータ構造がstackであり、後進先出の特徴が検出のニーズを満たす.検出の際、1文字ずつチェックし、左かっこであればスタックに入る、右かっこであれば現在のスタックトップ記号と右かっこであればスタックトップをポップアップして次の検出を行い、上記の2つの状況を満たさなければ、不正な文字が検出されたことを説明し、falseに戻る.
では、入力文字列(((([]))を例にとります.
ステップ1～3サイクル目、stackはスタックの3つの左カッコ(現在のスタックの上部は左カッコ)に入ります.
4ステップ目のループでは、stackはスタックの左方括弧[、現在のスタックの上部は左方括弧、スタック内の要素は1つの左方括弧に入ります.
5ステップ目のループでは、右方のカッコが見つかり、ちょうど現在のスタックの上部の左方のカッコ[左右のペアを満たすため、スタックを弾き、現在のスタックの上部は左のカッコに戻り、スタックの要素は3つの左のカッコになります.
6ステップ目のループでは、右カッコが発見され、現在のスタックトップの左カッコ(左右のペアを満たすため、スタックを弾き、現在のスタックトップは依然として左カッコを維持し、スタック内の要素は2つの左カッコである.
7ステップ目のループでは、右カッコが発見され、現在のスタックトップの左カッコ(左右のペアを満たすため、スタックを弾き、現在のスタックトップは依然として左カッコを維持し、スタック内の要素は1つの左カッコである.
8ステップ目のループでは、右カッコが見つかり、現在のスタックの上部の左カッコ(左右のペアを満たすため、スタックを弾き、スタック内の要素は0です.
入力文字列のループが完了すると、チェックstackが空になるのでtrueを返します.
コードは次のとおりです.
//2ms
#include <string>
#include <stack>
#include <iostream>
using namespace std;
class Solution {
public:
bool isValid(string s) {
int s_length=(int)s.length();
std::stack<char> left_char_stack;
for(int i=0;i<s_length;i++) {
if( (s[i]=='(') || (s[i]=='[') || (s[i]=='{') ){
left_char_stack.push(s[i]);
}else{
if(left_char_stack.empty())
return false;
char tmp= left_char_stack.top();
if( (tmp=='('&&s[i]==')') || (tmp=='['&&s[i]==']') || (tmp=='{'&&s[i]=='}') ){
left_char_stack.pop();
}else{
return false;
}
}
}
if(left_char_stack.empty())
return true;
else
return false;
}
};