sy3_2.c

数据结构实验与学习指导

/* sy3_2.c */
typedef char ElemType;      /*定义字符类型*/
#include "SQstack.h"
SeqStack OPTR, OPND;        /*定义前一个为操作符栈，后一个为操作数栈*/
char expr[255] = "";        /*存放表达式串*/
char *ptr = expr;
int step = 0;                /*计算的步次*/
int In(char ch)                /*判断字符是否为运算符子程序*/
{return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#');
}
void OutputStatus(void)     /*打印当前栈内状态及操作情况*/
{
  int p;
  printf("\n%-8d", ++step); /* step */
  for(p = 0; p <= OPTR.top; p++)/* OPTR */
    printf("%c",OPTR.elem[p]);
  printf("\t");
  for(p = 0; p <= OPND.top; p++)/* OPND */
     if (step==1)   printf("%c",' ');
     else  printf("%d ", OPND.elem[p]);
  printf("\t\t%c", *ptr);
 }
char Precede(char c1,char c2)
{/*判断运算符优先级*/
  int i=0,j=0;
  static char array[49]={ '>', '>', '<', '<', '<', '>', '>',
  '>', '>', '<', '<', '<', '>', '>',
  '>', '>', '>', '>', '<', '>', '>',
  '>', '>', '>', '>', '<', '>', '>',
  '<', '<', '<', '<', '<', '=', '!',
  '>', '>', '>', '>', '!', '>', '>',
  '<', '<', '<', '<', '<', '!', '='};
 switch(c1)
   {
     /*i为下面array的横标*/
     case '+' : i=0;break;
     case '-' : i=1;break;
     case '*' : i=2;break;
     case '/' : i=3;break;
     case '(' : i=4;break;
     case ')' : i=5;break;
     case '#' : i=6;break;
   }
 switch(c2)
  {  /*j为下面array的纵标*/
     case '+' : j=0;break;
     case '-' : j=1;break;
     case '*' : j=2;break;
     case '/' : j=3;break;
     case '(' : j=4;break;
     case ')' : j=5;break;
     case '#' : j=6;break;
    }
  return (array[7*i+j]);    /*返回运算符*/
 }
Operate(int a,char op,int b)
 { /*操作函数*/
     OutputStatus();
     printf("\tOPERATE(%d %c %d)", a, op, b);
    switch(op) {
     case '+' : return (a+b);
     case '-' : return (a-b);
     case '*' : return (a*b);
     case '/' : return (a/b);
     }
   return 0;
 }
int EvalExpr(void)
 {
   char c,theta,m,ch;
   int a,b,x,y;
   c = *ptr++;
   GetTop(&OPTR,&ch);
   while(c!='#'||ch!='#'){
   if(!In(c))
    {
      m=atoi(&c);/*转换为整型*/
      Push_SeqStack(&OPND,m);
      OutputStatus();
      printf("\tPUSH(OPRD, %d)",m);
      c = *ptr++;
     }
   else
    { GetTop(&OPTR,&ch);
      switch(Precede(ch,c))
      {
        case '<':
        Push_SeqStack(&OPTR,c);
       OutputStatus();
       printf("\tPUSH(OPRR,%c)",c);
        c = *ptr++;
        break;
      case '=':
         Pop_SeqStack(&OPTR,&ch);
         OutputStatus();
         printf("\tPOP(OPTR,%c)",ch);
         c = *ptr++;
         break;
      case '>':
         x=Pop_SeqStack(&OPTR,&ch);
         if (x==OK) theta=ch;
         y=Pop_SeqStack(&OPND,&ch);
         if (y==OK) b=ch;
         y=Pop_SeqStack(&OPND,&ch);
         if (y==OK) a=ch;
         Push_SeqStack(&OPND,Operate(a,theta,b));
       break;
     }/*switch*/
   }/*else*/
   GetTop(&OPTR,&ch);
}/*while*/
  if (GetTop(&OPND,&ch)==OK)
   return (ch);
}
int main(void)
  { printf("输入一个表达式(以#结束):");
    do{ gets(expr);
       }while(!*expr);            /*输入合法的表达式字符串*/
       InitStack_Sq(&OPTR);        /*初始化操作符栈*/
       OutputStatus();
       printf("\tPUSH(OPRR,#)");
       Push_SeqStack(&OPTR,'#');    /*将#压入操作符栈*/
       InitStack_Sq(&OPND );        /*初始化操作数栈*/
       printf("\n\n结果是:%d\n", EvalExpr());
       return 0;
   }