注册 登录
编程论坛 数据结构与算法

自己写了一个链栈操作,来实现括号匹配算法,但是程序运行不下去!求大神指教!

jj369258 发布于 2012-08-14 21:47, 662 次点击
#include<iostream>
#include<string.h>
#include<ctype.h>

using namespace std;
typedef struct snode
{
    char elem;
    struct snode *next;   
}Link,*Linkstack;

//Linkstack top;

int init_stack(Linkstack top)
{
   if(top->next==NULL)
   return 1;
   else
   return 0;
}

int empty(Linkstack top)//1空返回1,非空返回0
{
    if(top->next==NULL)
    return 1;
    else
    return 0;
}
void push_stack(Linkstack top,char a)//压栈
{
     Linkstack s;
     s=(Linkstack )malloc(sizeof(Link));
      s->elem=a;
     s->next=top->next;
     top->next=s;      
}
int pop_stack(Linkstack top,char a)//出栈
{
    if(empty(top))
    {
        cout<<"栈空!"<<endl;
        return 0;        
    }
    Linkstack s;
    s=(Linkstack )malloc(sizeof(Link));
    s=top->next;
    a=s->elem;
    top->next=s->next;
    free(s);
    return 1;
}
char getop(Linkstack top)//取栈顶元素,返回给a
{
    char a;
    if(empty(top))
    cout<<"栈空!"<<endl;
    a=top->next->elem;
    return a;
}
int main()
{
    Linkstack top;
    int i,length;
    char a,ch,str[100];
    cout<<"请输入要检测的括号对!"<<endl;
    cin>>str;
    length=strlen(str);
  for(i=0;i<length;i++)
  {
   if(str[i]=='('||str[i]=='['||str[i]=='{') /*如果是({【则入栈*/
          push_stack(top,str[i]);
   else
      {
          if(!empty(top))
          {
        ch=getop(top);
        if(ch=='('&&str[i]==')'||ch=='['&&str[i]==']'||ch=='['&&str[i]==']')
            pop_stack(top,a);
           else
           {
                cout<<"括号不匹配!"<<endl;
                return 0;
        }
         }
          else
              {
              cout<<"括号不匹配!"<<endl;
              return 0;
              }
         }                        
  }
    if(i==length&&empty(top))
     cout<<"括号匹配!"<<endl;
     else
     cout<<"括号不匹配!"<<endl;
     return 0;
}

2 回复
#2
stophin2012-08-17 17:10
#include<iostream>
#include<string.h>
#include<ctype.h>

using namespace std;
typedef struct snode
{
    char elem;
    struct snode *next;   
}Link,*Linkstack;

Linkstack init_stack()        //初始化不是像你那样的,头结点也要分配内存进行初始化,然后返回头结点指针
{
    Linkstack top=(Linkstack)malloc(sizeof(Link));
    top->next=NULL;
    return top;
}

int empty(Linkstack top)//1空返回1,非空返回0
{
    if(top->next==NULL)
        return 1;
    else
    return 0;
}
void push_stack(Linkstack top,char a)//压栈
{
     Linkstack s;
     s=(Linkstack )malloc(sizeof(Link));
      s->elem=a;
     s->next=top->next;
     top->next=s;      
}
int pop_stack(Linkstack top,char a)//出栈
{
    if(empty(top))
    {
        cout<<"栈空!"<<endl;
        return 0;        
    }
    Linkstack s;        //出栈就不需要给s分配内存了,s只作为一个指针来用
    s=top->next;
    a=s->elem;
    top->next=s->next;
    free(s);
    return 1;
}
char getop(Linkstack top)//取栈顶元素,返回给a
{
    char a;
    if(empty(top))
    {
        cout<<"栈空!"<<endl;
        return '\0';
    }
    a=top->next->elem;
    return a;
}
int main()
{
    Linkstack top;
    top=init_stack();
    int i,length;
    char a,ch,str[100];
    cout<<"请输入要检测的括号对!"<<endl;
    cin>>str;
    length=strlen(str);
      for(i=0;i<length;i++)
      {
       if(str[i]=='('||str[i]=='['||str[i]=='{') /*如果是({[则入栈*/
              push_stack(top,str[i]);
       else
       {
            if(!empty(top))
            {
                ch=getop(top);
                if(ch=='('&&str[i]==')'||ch=='['&&str[i]==']'||ch=='{'&&str[i]=='}')    //这边写了两个[]
                    pop_stack(top,a);
                else
                {
                        cout<<"括号不匹配!"<<endl;
                        return 0;
                }
             }
             else
             {
                  cout<<"括号不匹配!"<<endl;
                  return 0;
            }
        }                        
      }
    if(i==length&&empty(top))
         cout<<"括号匹配!"<<endl;
     else
        cout<<"括号不匹配!"<<endl;
     return 0;
}

#3
枫の月影2012-08-18 14:50
看不懂
1