一.初级括号匹配
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;
}