随笔-27  评论-6  文章-0  trackbacks-0
/*
括号匹配问题,比较经典,利用堆栈来实现(摘自internet)

1. 括号匹配的四种可能性:

①左右括号配对次序不正确
②右括号多于左括号
③左括号多于右括号
④左右括号匹配正确

2. 算法思想:

顺序扫描算数表达式(表现为一个字符串),当遇到三种类型的左括号时候让该括号进栈;
当扫描到某一种类型的右括号时,比较当前栈顶元素是否与之匹配,若匹配,退栈继续判断;
若当前栈顶元素与当前扫描的括号不匹配,则左右括号配对次序不正确;
若字符串当前为某种类型的右括号而堆栈已经空,则右括号多于左括号;
字符串循环扫描结束时,若堆栈非空(即堆栈尚有某种类型的左括号),则说明左括号多于右括号;
否则,括号配对正确。

3. 程序实现:
*/
#include 
<iostream>
using namespace std;

#define maxsize 100

struct sStack
{
     
char sign[maxsize];
     
int top;
};

int InitsStack(sStack &SS)
{
     SS.top
=-1;
     
return 1;
}

int IsEmptysStack(sStack &SS)
{
     
if(SS.top==-1)
         return 1;
     
return 0;
}

int PushsStack(sStack &SS,char c)
{
     SS.sign[
++SS.top]=c;
     
return 1;
}

int UpsStack(sStack &SS)
{
    
if(IsEmptysStack(SS))
    {
         cout
<<"栈空"<<endl;
        
return 0;
    }
    SS.top
--;
    
return 1;
}

char TopsStack(sStack &SS)
{
    
if(IsEmptysStack (SS))
    {
         cout 
<<"栈空"<<endl;
        
return 0;
    }
    
return SS.sign[SS.top];
}

int main()
{
     
string s;
     cout
<<"输入表达式:";
     cin
>>s;
     
int length=s.length();
     
int i;
     sStack SS;
     InitsStack(SS);
     
for(i=0;i<length;++i)
     {
           
if(s[i]=='('||s[i]=='['||s[i]=='{')
                    PushsStack(SS,s[i]);
           
else if(s[i]==')'&&!IsEmptysStack(SS)&&TopsStack(SS)=='(')
                UpsStack(SS);         
           
else if(s[i]==')'&&!IsEmptysStack(SS)&&TopsStack(SS)!='(')
                    cout
<<"括号匹配次序不正确"<<endl;
           
else if(s[i]==']'&&!IsEmptysStack(SS)&&TopsStack(SS)=='[')
                    UpsStack(SS);
           
else if(s[i]==']'&&!IsEmptysStack(SS)&&TopsStack(SS)!='[')
                    cout
<<"括号匹配次序不正确"<<endl;
           
else if(s[i]=='}'&&!IsEmptysStack(SS)&&TopsStack(SS)=='{')
                    UpsStack(SS);
           
else if(s[i]=='}'&&!IsEmptysStack(SS)&&TopsStack(SS)!='{')
                    cout
<<"括号匹配次序不正确"<<endl;
           
else if((s[i]==')'||s[i]==']'||s[i]=='}')&&IsEmptysStack(SS))
                    cout
<<"右括号多于左括号"<<endl;
     }
     
if(!IsEmptysStack(SS))
           cout
<<"左括号多于右括号"<<endl;
     
else if(i=(length-1)&&IsEmptysStack(SS))
           cout
<<"括号匹配正确"<<endl;
               
     system(
"PAUSE");
     
return 0;
}

posted on 2010-09-12 23:11 CrazyNerd 阅读(3605) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理