かっこ一致(C++)

1359 ワード

アルゴリズムの考え方:
入力した文字列を巡回します.
左かっこにぶつかるとスタックを押す.右カッコに遭遇し、スタックが空でない場合は、スタックの上部の左カッコを取り出し、一致してbool値を返します.
ループが終了するまでエラーが発生せず、スタックが空の場合、一致は成功します.
アルゴリズム設計:
bool  check(string s)

{    stack p
   bool flag

    for  i  to  s.length() :

            if ( left (s[i]) ) p.push(s[i])

            if ( right(s[i]) ) :

                    if( !s.empty() && match(s.top(),s[i]) ):
                        s.pop()
         
           else flag=false;
}

テスト例:
(()){}
(qw){[]}
 
#include
#include
#include
#include


using namespace std;

bool left(char s)
{
    return s=='('||s=='{'||s=='[';
}
bool right(char s)
{
    return s==')'||s=='}'||s==']';
}
bool check(char a,char b)
{
    return (a=='('&&b==')') || (a=='{'&&b=='}')||(a=='['&&b==']');
}

bool match(string s)
{
    stack p;
    bool flag=true;

    for(int i=0;i>n;
    cin.ignore(1, '
'); for(int i=0;i