test04_2.cpp

该包是数据结构的实验软件,来源于合肥工业大学人工智能与数据挖掘实验室,用来实现数据结构.

//{ test04_2 }
#include"sstack.h"
const maxsize=20;
int i=0;
struct stack
     {
       int data[maxsize];
       ____________ //{blank1}
      };
stack st1,st2;

unsigned char sexp[40];

void   setnull(stack& s)
  {
     ____________// {blank 2}
  }
boolean   Empty(stack& s)
  { boolean Empty=boolean(s.top==0);

      _____________ //{blank 3}
   }
int   Top(stack& s)
 {
     if  (Empty(s) )
	    Error_exit("Empty, cannot get top");
     else
      {int Top= ___________________ //{blank 4}
       return Top;
       }
}
  void   Push(stack& s,int  x)
{
     if  ___________________ //{blank 5}
    Error("Overflow");
     else
	{s.top=s.top+1;
	  ____________________________ //{blank 6}
	}
  }

int   Pop(stack& s)
  {  int Pop;
     if (s.top==0)
       Error("Down Overflow of stack ");
     else
       {  Pop=s.data[s.top];
	 s.top=s.top-1;
	}
  return Pop;
 }

boolean  Is_Num(char c)
{ boolean Is_num=(c=='0'||c=='1'||c=='2'||c=='3'||c=='4'||c=='5'||c=='6'||c=='7'||c=='8'||c=='9');
   return Is_num;
   }

 boolean  Is_Lower(char c)
 { char ctop;
  boolean Is_Lower=false;
     if  (Empty(st1)  )
	 Is_Lower=false;
     else
     {      ctop=Top(st1);
	    if (c=='+'||c=='-'||c==')'||c=='#')
	       Is_Lower=(ctop=='+'||ctop=='-'||ctop=='*'||ctop=='/'||ctop==')');
	    else if (c=='*'||c=='/')
		  Is_Lower=(ctop=='*'||ctop=='/'||ctop==')');
		 else
		    Is_Lower=false;
	  }
   return Is_Lower;
  }

 boolean  Is_Equal(char c)
  { char ct;
    boolean Is_Equal=false;

      if  (Empty(st1) )
	 Is_Equal=false;
      else
	   {ct= Top(st1);
	    Is_Equal=boolean ((ct=='#'&&c=='#')||(ct=='('&& c==')') );

	   }
    return Is_Equal;
   }

 void  comput()
  {// comput: two number at top &top-1, operator, result to stack2
    char opr;
    int n1,n2,nr;
    n2=Pop(st2);
    n1= Pop(st2);
    opr=char(Pop(st1));

    switch(opr)
    {
    case   '+':nr=n1+n2; break;
    case   '-':nr=n1-n2;break;
    case   '*':nr=n1*n2;break;
    case   '/':if (n2==0)
		    Error_exit("Divided by 0 ");
		 else
		    nr=n1/n2;
   }

	Push(st2,nr);
   }


  void  Getchar(char& c,unsigned char sexp[])
    {   while (i<strlen(sexp)&& (sexp[i]==' '))
	       i=i+1;
	    c=sexp[i];

	    i=i+1;
    }
  void  getchar1(char& c,unsigned char sexp[])
   {   c=sexp[i];
       i=i+1;
       }

  void  compute_expp(string sexp)
 { char  c,ctemp;
   int s;
   boolean suc;
    i=0;
   cout<<sexp<<"=";
   unsigned char ss[20]="#";
   strcat(ss,sexp);
   strcat(ss,"#");
   strcpy(sexp,ss);
    setnull(st1);
    setnull(st2);

    suc=false;
    do
       {
       Getchar(c,sexp);

       s=0;
       if (Is_Num(c) )
	   { while (Is_Num(c))
		   { s=s*10+c-'0';
		     getchar1(c,sexp) ;
		     }
		 Push(st2,s);
	   }
      if (!(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#') )
	 Error("Input error:");
      else if ( Empty(st1)  )
	     Push(st1,c);
	   else
	     {  while (!Empty(st1)&&Is_Lower(c) )
			    comput();
		       if (!Empty(st1)&&Is_Equal(c) )
			 {  ctemp=Pop(st1);
			    suc=c=='#';
			  }
		       else
			 Push(st1,c);
	      }
    }
    while(!suc);
    cout<<Pop(st2);
 }

main()

  { Into_graph();
  compute_expp("12+3*4+50/2");
  getch();
  strcpy(sexp,"");
  cout<<endl;
  unsigned char sss[]="Input expression:";
  cout<<sss;
  cin>>sexp;
  compute_expp(sexp);
  getch();

}