括号匹配（C++)

　

括号匹配

算法思想：

将输入的字符串遍历。

遇到左括号就压栈；遇到右括号，若栈不为空，就将栈顶的左括号取出，匹配返回一个bool值。

若直至遍历结束都没有发生错误且栈为空，则匹配成功。

算法设计：

bool  check(string s)

{    stack<char> p
　　　ｂｏｏｌ　ｆｌａｇ

    for  i  to  s.length() :

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

            if ( right(s[i]) ) :

                    if(　!s.empty()　＆＆　ｍａｔｃｈ（ｓ．ｔｏｐ（），ｓ［ｉ］）　)：
                        ｓ．ｐｏｐ（）
　　　　　　　  
　　　　　　　　　　　ｅｌｓｅ　ｆｌａｇ＝ｆａｌｓｅ；
}

测试例子：

(()){}

(qw){[]}

#include<iOStream>
#include<stack>
#include<cstdlib>
#include<cstring>


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<char> p;
    bool flag=true;

    for(int i=0;i<s.length();i++)
    {
       if(left(s[i]))
       {
           p.push(s[i]);
       }
       if(right(s[i]))
       {
           if(!p.empty()&&check(p.top(),s[i]))
           {
               p.pop();
           }
           else flag=false;
       }

    }
    if(!p.empty())flag=false;
    return flag;
}

int main()
{
    int n;
    cin>>n;
    cin.ignore(1, '\n');
    for(int i=0;i<n;i++)
    {

     string str;
     getline(cin,str);//读入string
    if(match(str))
     {
        cout<<"Yes"<<endl;
     }
     else cout<<"No"<<endl;
    }
}

文章最后发布于: 2018-09-14 17:28:05

相关阅读

} expectedcss(css-rcurlyexpected)

} expectedcss(css-rcurlyexpected)----我出现这个错误的原因是没有在style中添加lang=less，添加后变为正常

HttpServeltResponse接口中sendRedirect方法详解

请求重定向HTTP协议规定了一种重定向机制：用户在浏览器端输入特定的URL，请求访问服务器端的某个组件服务器端的组件返回一个状态代

array_column()函数用法

array_column()作用  返回输入数组中某个单一列的值。语法   array_column(array,column_key,index_key);参数介绍  array:

Tomcat服务器安装配置部署

首先下载tomcat服务器： tomcat是一个免费开源的服务器，可以到官方网站：http://tomcat.apache.org/下载，jdk每更新一个版本，tomcat就会

Invalidate、InvalidateRect详解

转自：http://www.cppblog.com/Raycruiser/articles/44193.htmlInvalidateRect只是增加重绘区域，在下次WM_PAINT的时候才生效Invalid