以字符序列的形式从终端输入语法正确的,不含变量的整数表达式.实现对算术四则混合运算表达式的值.利用栈来实现.

#include
#include
#include
#define  true 1
#define  false 0
#define  ok 1
#define  error 0
#define  overflow  -2
#define  STACK_INIT_SIZE 100
#define  STACKINCERMENT 10
typedef  int status;
typedef  int operandtype;
typedef  char operatortype;
typedef  struct sqstack{
       int *base;
       int *top;
       int stacksize;
}sqstack;
char a[8][8]={
    {'\0','+','-','*','/','(',')','#'},
    {'+','>','>','<','<','<','>','>'},
    {'-','>','>','<','<','<','>','>'},
    {'*','>','>','>','>','<','>','>'},
    {'/','>','>','>','>','<','>','>'},
    {'(','<','<','<','<','<','=','\0'},
    {')','>','>','>','>','\0','>','>'},
    {'#','<','<','<','<','<','\0','='}};

status in(char c)  //判断c是否运算符函数
{  if(c<'0'||c>'9')
       return true;
   else
       return false;
}

status initstack(sqstack &s)           //初始化栈函数
{  s.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));
   if(!s.base)   exit(overflow);
   s.top=s.base;
   s.stacksize=STACK_INIT_SIZE;
   return ok;
}

status gettop(sqstack s, int &e)           //取栈顶元素函数
{  if(s.top==s.base)  
       return error;
   e=*(s.top-1);
   return ok;
}

status push(sqstack &s,int e)         // 压栈函数
{  if(s.top-s.base>=s.stacksize){
        s.base=(int *)realloc(s.base,(s.stacksize+STACKINCERMENT)*sizeof(int));
        if(!s.base) exit(overflow);
        s.top=s.base+s.stacksize;
        s.stacksize+=STACKINCERMENT;
   }
   *s.top++=e;
   return ok;
}

status pop(sqstack &s,int &e)  //出栈函数
{  if(s.top==s.base)  
       return error;
   e=*--s.top;
   return ok;
}

operatortype precede(operatortype c1,operatortype c2)   //判断两个运算符优先级函数
{  int i,j;
   for(i=0;i<8&&a[i][0]!=c1;i++);       //从第0列查找操作符c1
   if(i>=8){
       printf("Operator error!/n");
       exit(error);
   }
   for(j=0;j<8&&a[0][j]!=c2;j++);      //从第0行查找操作符c2
   if(j>=8){
       printf("Operator error!/n");
       exit(error);
   }
   return a[i][j];
}

status stackempty(sqstack s)   //判断栈是否为空函数
{  if(s.base==s.top)
       return true;
   else
       return false;
}

status check(char *str)      //查看表达式括号是否匹配函数
{  int i=0,e;
   sqstack s;
   initstack(s);
   while(str[i]!='#')
   {  switch(str[i]){
          case'(': push(s,str[i]);  break;
          case'[': push(s,str[i]);  break;
          case')': if(pop(s,e))
                   {  if(e=='(')
                         break;
                       else
                         return error;
                   }
                   else  return error;
          case']': if(pop(s,e))
                   {  if(e=='[')
                         break;
                       else
                         return error;
                   }
                   else  return error;
     }
     i++;
   }
   if(stackempty(s))
       return ok;
   else
       return error;
}

operandtype operate(operandtype a,operatortype thera,operandtype b)  //求两个元素通过指定运算的结果函数
{  switch(thera){
      case'+': return a+b;
      case'-': return a-b;
      case'*': return a*b;
      case'/': if(b==0)
               {  printf("Divide zero!\n");  //除数为0,程序结束
                  exit(overflow);
               }
               else
                   return a/b;
    default: printf("Operator error!\n");  //操作符错误,程序结束
             exit(error);
  }
}
                  
operandtype evaluate_expression(char *str)  //求表达式值函数
{  int i=0,value,e,t,a,b,thera,buffer;
   char c;
   sqstack optr,opnd;
   initstack(optr);  initstack(opnd);
   push(optr,'#');
   c=str[i];
   gettop(optr,e);
   while(c!='#'||e!='#')
   {  if(!in(c)){
          buffer=c-'0';
          do{  if(!in(str[i+1])){
                    buffer*=10;
                    buffer+=(str[i+1]-'0');
                    i++;
               }  
          }while(!in(str[i+1]));
          push(opnd,buffer);  
          i++;
          c=str[i];
       }
       else
           switch(precede(e,c)){
                case'<':  push(optr,c); c=str[++i];
                          break;
                case'=':  pop(optr,t); c=str[++i]; // 消去括号
                          break;
                case'>':  pop(optr,thera);
                          pop(opnd,b);   pop(opnd,a);
                          push(opnd,operate(a,thera,b));  //求值并压栈
                          break;
         }
       gettop(optr,e);
   }
   gettop(opnd,value);
   return value;
}

void main()      //主函数
{  char str[STACK_INIT_SIZE],c;
   int flag,t;
   do{  flag=1;
        while(flag)
        {  printf("Input a string,end with #:\n");
           scanf("%s",str);       //str用来存放字符串
           if(check(str))
              flag=0;
           else
           {  flag=1;
              printf("Input error,Retry!\n");  //符号不匹配则重新输入
           }
        }
        t=evaluate_expression(str);
        printf("The result:%d\n",t);
        printf("Continue or not?(y/n):");
        getchar();
        c=getchar();
   }while(c=='y'||c=='Y');  //实现多次输入
   getch();
}

评论