知行社区

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 3114|回复: 0
收起左侧

栈求表达式的值(有一点问题,大家帮忙看看)

[复制链接]
euiuxsw 发表于 2012-1-7 02:54 | 显示全部楼层 |阅读模式
/*表达式求值(范围为int类型,输入负数要用(0-正数)表示)   */
  typedef   int   SElemType;   /*   栈元素类型为整型   */
  #include <string.h>
  #include <ctype.h>
  #include <malloc.h>    /*   malloc()等   */
  #include <limits.h>    /*   INT_MAX等   */
  #include <stdio.h>     /*   EOF(=^Z或F6),NULL   */
  #include <stdlib.h>    /*   atoi()   */
  #include <io.h>        /*   eof()   */
  #include <math.h>      /*   floor(),ceil(),abs()   */
  #include <process.h>   /*   exit()   */
  /*   函数结果状态代码   */
  #define   TRUE   1
  #define   FALSE   0
  #define   OK   1
  #define   ERROR   0
  #define   INFEASIBLE   -1
  typedef   int   Status;   /*   Status是函数的类型,其值是函数结果状态代码,如OK等   */
  typedef   int   Boolean;   /*   Boolean是布尔类型,其值是TRUE或FALSE   */

  #define   STACK_INIT_SIZE   10   /*   存储空间初始分配量   */
  #define   STACKINCREMENT   2   /*   存储空间分配增量   */
  typedef   struct   SqStack
  {
      SElemType   *base;   /*   在栈构造之前和销毁之后,base的值为NULL   */
      SElemType   *top;   /*   栈顶指针   */
      int   stacksize;   /*   当前已分配的存储空间,以元素为单位   */
  }SqStack;   /*   顺序栈   */


  /*   顺序栈的基本操作(9个)   */
  Status   InitStack(SqStack   *S)
  {   /*   构造一个空栈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;
  }

  Status   DestroyStack(SqStack   *S)
  {   /*   销毁栈S,S不再存在   */
      free((*S).base);
      (*S).base=NULL;
      (*S).top=NULL;
      (*S).stacksize=0;
      return   OK;
  }

  Status   ClearStack(SqStack   *S)
  {   /*   把S置为空栈   */
      (*S).top=(*S).base;
      return   OK;
  }

  Status   StackEmpty(SqStack   S)
  {   /*   若栈S为空栈,则返回TRUE,否则返回FALSE   */
      if(S.top==S.base)
          return   TRUE;
      else
          return   FALSE;
  }

  int   StackLength(SqStack   S)
  {   /*   返回S的元素个数,即栈的长度   */
      return   S.top-S.base;
  }

  Status   GetTop(SqStack   S,SElemType   *e)
  {   /*   若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR   */
      if(S.top> S.base)
      {
          *e=*(S.top-1);
          return   OK;
      }
      else
          return   ERROR;
  }

  Status   Push(SqStack   *S,SElemType   e)
  {   /*   插入元素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).top=(*S).base+(*S).stacksize;
          (*S).stacksize+=STACKINCREMENT;
      }
      *((*S).top)++=e;
      return   OK;
  }

  Status   Pop(SqStack   *S,SElemType   *e)
  {   /*   若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR   */
      if((*S).top==(*S).base)
          return   ERROR;
      *e=*--(*S).top;
      return   OK;
  }

  Status   StackTraverse(SqStack   S,Status(*visit)(SElemType))
  {   /*   从栈底到栈顶依次对栈中每个元素调用函数visit()。   */
      /*   一旦visit()失败,则操作失败   */
      while(S.top> S.base)
          visit(*S.base++);
      printf( &quot;\n &quot;);
      return   OK;
  }

  SElemType   Precede(SElemType   t1,SElemType   t2)  
  {   /*   判断两符号的优先关系   */
      SElemType   f;
      switch(t2)
      {
          case   '+':
          case   '-':if(t1=='('||t1=='=')
                                f= '<';
                            else
                                f='>';
                            break;
          case   '*':
          case   '/':if(t1=='*'||t1=='/'||t1==')')
                                f= '>';
                            else
                                f='<';
                            break;
          case   '(':if(t1==')')
                            {
                                printf(&quot;ERROR1\n&quot;);
                                exit(ERROR);
                            }
                            else
                                f= '<';
                            break;
          case   ')':switch(t1)
                            {
                                case   '(':f='=';
                                                  break;
                                case   '=':printf(&quot;ERROR2\n&quot;);
                                                  exit(ERROR);
                                default:   f='>';
                            }
                            break;
          case   '=':switch(t1)
                            {
                                case   '=':f='=';
                                                  break;
                                case   '(':printf(&quot;ERROR2\n&quot;);
                                                  exit(ERROR);
                                default:   f='>';
                            }
      }
      return   f;
  }

  Status   In(SElemType   c)  
  {   /*   判断c是否为运算符   */
      switch(c)
      {
          case '+':
          case '-':
          case '*':
          case '/':
          case '(':
          case ')':
          case '=':return   TRUE;  
          default:return   FALSE;
      }
  }

  SElemType   Operate(SElemType a,SElemType theta,SElemType b)  
  {
      SElemType c;
      switch(theta)
      {
          case '+':c=a+b;
                          break;
          case '-':c=a-b;
                          break;
          case '*':c=a*b;
                          break;
          case '/':c=a/b;
      }
      return   c;
  }

  SElemType   EvaluateExpression()  
  {   /*   算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈   */
      SqStack   OPTR,OPND;
      SElemType   a,b,d,x,theta;
      char   c;   /*   存放由键盘接收的字符串   */
      char   z[6];   /*   存放整数字符串   */
      int   i;
      InitStack(&OPTR);   /*   初始化运算符栈   */
      Push(&OPTR, '=');   /*   =是表达式结束标志   */
      InitStack(&OPND);   /*   初始化运算数栈   */
      c=getchar();
      GetTop(OPTR,&x);
      while(c!='='||x!='=')
      {
          if(In(c))   /*   是7种运算符之一   */
              switch(Precede(x,c))
              {
                  case '<':Push(&OPTR,c);   /*   栈顶元素优先权低   */
                                  c=getchar();
                                  break;
                  case '=':Pop(&OPTR,&x);   /*   脱括号并接收下一字符   */
                                  c=getchar();
                                  break;
                  case '>':Pop(&OPTR,&theta);   /*   退栈并将运算结果入栈   */
                                  Pop(&OPND,&b);
                                  Pop(&OPND,&a);
                                  Push(&OPND,Operate(a,theta,b));
              }
          else if(c>='0'&&c<='9')   /*   c是操作数   */
          {
              i=0;
              do
              {
                  z=c;
                  i++;
                  c=getchar();
              }while(c>='0'&&c<='9');
              z=0;
              d=atoi(z);   /*   将字符串数组转为整型存于d   */
              Push(&OPND,d);
          }
          else   /*   c是非法字符   */
          {
              printf( &quot;ERROR3\n&quot;);
              exit(ERROR);
          }
          GetTop(OPTR,&x);
      }
      GetTop(OPND,&x);
      return  x;
  }

  int main()
  {
      printf( &quot;请输入算术表达式,负数要用(0-正数)表示,并以=结束\n&quot;);
      printf( &quot;%d\n&quot;,EvaluateExpression());
      return 0;
  }

QQ|小黑屋|手机版|知行技术社区 ( 湘ICP备11020288号-1 )

GMT+8, 2020-9-29 17:41 , Processed in 0.018374 second(s), 7 queries , Redis On.

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表