括号匹配问题

一.初级括号匹配

1.括号匹配原则:

右括号“)”与前面最近的尚未配对的左括号“(”匹配,“(”具有最先扫描到的最后匹配的特点。

后到先处理,因此可以使用栈

有以下这些不匹配的情况:

  • (1+2)*(3-4)+5(+6
  • (1+2*(3-4)+(5-2)+6
  • )2+3(

2.过程分析:

输入:字符串str存储的算术表达式

输出:0表示匹配,1表示多左括号,-1表示多右括号

(1)定义顺序栈s

(2)读取str[i]中的字符:

  •    若为‘(’则入栈
  •    若为')'且栈非空,则从栈中弹出一个‘(’,说明二者相匹配;
  •     若为')'且栈空,则返回-1

(3)扫描字符串完成后:

  •     若栈空,则返回0,说明括号匹配
  •     若栈非空,则返回1,说明多左括号

3.具体实现:

#include <iostream>
//括号匹配问题
using namespace std;

class Matcher{
public:
    Matcher(string str);
    ~Matcher();
    int match();
private:
    string str;
};
Matcher::Matcher(string str){
    this->str=str;
}
Matcher::~Matcher(){

}
Matcher::match(){
    char s[100];//顺序栈
    int i,top;
    top=-1;
    for(i=0;str[i]!='\0';i++){
        if(str[i]==')')
           if(top>-1)//出栈前判断是否为空
           top--;
           else return -1;//栈空,多右括号
        else if(str[i]=='(')
                s[++top]=str[i];//入栈
    }
    if(top==-1)
        return 0;//匹配
    else return 1;//栈中有左括号,多左括号
}
int main()
{
    string str;
    cout<<"请输入一个算术表达式:"<<endl;
    cin>>str;
    Matcher m(str);
    int k=m.match();
    if(k==0)
        cout<<"括号匹配"<<endl;
    else if(k==1)
        cout<<"多左括号"<<endl;
    else if(k==-1)
        cout<<"多右括号"<<endl;
    return 0;
}

二.复杂括号匹配

1.括号匹配原则:有{},[],()三种括号,不允许三种括号的左右括号相互匹配

   比如{)、[}、(}、(]都是错误的

2.过程分析:

输入:字符串str存储的算术表达式

输出:0表示匹配,1表示多左括号,-1表示多右括号

(1)定义顺序栈s

(2)读取str[i]中的字符:

  •    若为‘(’、‘[’、‘{’则入栈
  •    若为')'、‘]’、‘}’且栈非空,则从栈中弹出一个左括号,并比较左右括号是否同级匹配;
  •    若为')'、‘]’、‘}’且栈空,则返回-1

(3)扫描字符串完成后:

  •     若栈空,则返回0,说明括号匹配
  •     若栈非空,则返回1,说明多左括号

3.具体实现:

#include <iostream>
//复杂括号匹配问题
using namespace std;

class Matcher{
public:
    Matcher(string str);
    ~Matcher();
    int match();
private:
    string str;
};
Matcher::Matcher(string str){
    this->str=str;
}
Matcher::~Matcher(){

}
Matcher::match(){
    char s[100];//顺序栈
    int i,top;
    top=-1;
    for(i=0;str[i]!='\0';i++){
        switch(str[i]){
        case ')':{
            if(s[top]=='('&&top>-1)//判断是否同级匹配,出栈前是否为空
                top--;
            else
                return 1;//不匹配或者栈空,多右括号
        }
        case '}':{
             if(s[top]=='{'&&top>-1)
                top--;
            else
                return 1;
             }
        case ']':{
             if(s[top]=='['&&top>-1)
                top--;
            else
                return 1;
        }
        }
        if((str[i]=='(')||(str[i]=='[')||(str[i])=='{')
                s[++top]=str[i];//入栈
        }

    if(top==-1)
        return 0;//匹配
    else
        return 1;
}
int main()
{
    string str;
    cout<<"请输入一个算术表达式:"<<endl;
    cin>>str;
    Matcher m(str);
    int k=m.match();
    if(k==0)
        cout<<"括号匹配"<<endl;
    else if(k==1)
        cout<<"括号不匹配"<<endl;
    return 0;
}

上一篇:Android使用百度语音识别api代码实现。


下一篇:去掉指定字符串的开头的指定字符