求一个栈的操作和实现程序 - 编程论坛

#2

小小小火柴2012-10-30 21:07

首先，这个程序的作用只是判断（）是否配对，并没有其他作用！

#include<iostream>
using namespace std;
class link
{
public:
    char data;
    link *next;
};
class linkstack
{
public:
    link *top;
    void inistack()//栈的初始化
    {
        top=new link;
        top->next=NULL;
    }
    void push(char x)//进栈
    {
        link *s=new link;
        s->data=x;
        s->next=top->next;
        top->next=s;
    }
    void pop()//退栈
    {
        link *s=top->next;
        if(s!=NULL)
        {
            top->next=s->next;
            delete s;
        }
    }
    char gettop()
    {
        if(top->next!=NULL)
            return (top->next->data);
        else return NULL;
    }
    bool empty()
    {
        if(top->next==NULL)
            return true;
        else return false;
    }
    int yn()
    {
        char c;
        int sign=1;
        inistack();
        cout<<"请输入表达式，并以=结束：";
        c=getchar();
        while(c!='=')
        {
            switch(c)
            {
            case '('://扫描到'('入栈
                push(c);
                break;
            case ')':
                {if(gettop()=='(')
                     pop();
                 else
                     sign=0;
                 break;}
            }
            if(sign==0)
                break;
            else
                c=getchar();

        }
        if(!empty())
            sign=0;
        return sign;
    }
    void judgeout(int a)
    {
        if(a==1)
            cout<<"括号配对正确\n";
        else if(a==0)
            cout<<"括号配对错误\n";
    }

};
void main()
{   int n;
    linkstack s;
    n=s.yn();
    s.judgeout(n);
}

#3

凌云飞翔2012-11-01 00:29

   建栈时要多注意指针的传送，取地址等细节方面的东西。。。

#include  <stdio.h >
#include <stdlib.h>
#define  OVERFLOW   -2
#define  OK  1
#define STACK_INIT_SIZE   100
#define  STACKINCREMENT  10
typedef  char SElemType  ;
typedef   int Status   ;
typedef struct {
      SElemType  *base   ;
      SElemType  *top    ;
      int  stacksize  ;
}  SqStack    ;
Status    StackEmpty  (SqStack  s  )
{ if  (s.base==s.top)  return 1;
    else  return 0  ;
} //stackempty
Status  InitStack  (SqStack  &s)
{  s.base=(SElemType  *)malloc (STACK_INIT_SIZE *sizeof (SElemType ))  ;
    if (!s.base)  exit (OVERFLOW )   ;
     s.top = s.base ;
     s.stacksize =STACK_INIT_SIZE ;
     return  OK  ;
}//initstack
Status  Push (SqStack &s  ,SElemType e  )
{  if (s.top -s.base >=s.stacksize )//栈满，追加存储空间
{   s.base = (SElemType *) realloc (s.base,(s.stacksize +STACKINCREMENT)
                                    *sizeof (SElemType) )  ;
        if (!s.base) exit  ( OVERFLOW ) ;//存储分配失败
        s.stacksize +=STACKINCREMENT  ;
}
         *s.top++=e  ;
        return  OK  ;
}//push
Status Pop  (SqStack  &s  , SElemType *e)
{ if  (s.top==s.base  ) return  0  ;

  *e =*--s.top ;
  return  OK  ;
}// pop
Status GetTop (SqStack s  ,SElemType  *e )
{  if (s.top ==s.base ) return  0   ;
*e = *(s.top-1)  ;
return  1 ;
}//gettop
main ()
{  int  i=0  ;
SqStack    s  ;
    char a[20]={0}  , ch ,e  ;
   InitStack  ( s) ;
printf ("请输入括号且长度不能超过20 :\n")  ;
while ((ch=getchar())!='\n')
{   a[i]=ch  ;
     i++  ;

}
for  (i=0 ;a[i]!='\0' ;i++)
{  switch  (a[i])
{        case '(' :  ;
         case '[' : ;
         case '{' :
             { Push (s ,a[i])  ; break  ; }
         case ')' : ;
         case '}' : ;
         case ']' :
                   if  (StackEmpty  (s ))
                 {printf ("括号不匹配\n")  ; return  ;}
                else    {  GetTop (s,&e)  ;
                   if  ((a[i]-e==1)||(a[i]-e==2))
                   { Pop (s,&e)  ;  break ;}

             }

}
}
   if ( StackEmpty (s))
   printf ("括号匹配\n") ;
    else  printf ("括号不匹配\n") ;
}

#4

红晓可乐2012-11-01 18:12

#5

狼贲2012-11-03 08:11

回复 4楼红晓可乐

谢谢。

#6

gaolongtou2012-11-03 08:44