《数据结构》课程设计

表达式求值

 班级：  

学号：  

姓名：   

指导老师：

表达式求值

1、     问题描述

要求对包含加、减、乘、除、括号运算符的任意整型表达式进行求解。

2、     设计思路

这个程序的关键是对数字与运算符的判断和运算符优先级的判断，以及出栈的运算。建立两个栈，分别存储数字与运算符，栈1存运算符，栈2存数字。依次读取表达式的字符串，先判断是数字还是运算符，如果是数字不能马上压入栈2，因为可能是大于10的数字，应该继续循环，如果还是数字，则利用计算保存数值，直到指到运算符时停止，将计算后的数字压入栈2。压入运算符之前先将要压入的与栈顶的运算符优先级相比较，如果栈顶是‘（’而当前不是‘）’，则不需比较优先级，直接压入；如果栈顶是‘（’，当前是‘）’，则抵消（弹出‘（’，指向表达式下一个字符）；若当前的运算符优先级大于栈顶的，则压入；若当前的运算符优先级小于栈內时，弹出栈顶的运算符，同时弹出两组数字，经过运算符的运算后再重新压到栈内。为了方便判断运算结束，在存储运算符之前先将‘#’压入栈1中，在输入表达式时以“#”结束，所以可以以运算符==‘#’并且栈1顶==‘#’来结束运算，弹出栈2的数值，即为表达式求值的最终结果。

上述操作的算法步骤：

（1）初始化算符S1,数字栈S2;，将‘#’压入算符栈S1中。

（2）读表达式字符=>w。

（3）当栈顶为‘#’并且w也是‘#’时结束；否则循环做下列步骤：

（3-1）如果w是数字，存储到m，再经过计算存储到num中。m=w-‘0’;num=num*pow(10,n)+m;n++;读下一个字符=>w，如果是运算符，则跳出循环；转3-2。

（3-2）w若是运算符，则：

   （3-2-1）如果栈顶为‘（’并且w为‘）’则‘（’出栈，读下一个字符=>w；转（3）。

      （3-2-2）如果栈顶为‘（’或者栈顶优先级小于w优先级，则w入栈，读下一个字符=>w；转（3）。否则：从算符栈中出栈，并从数字栈中弹出两组数字进行运算，将结果重新压入数字栈，转（3）。

3、     数据结构设计

前面提到，要用栈存储数据，由于一个数字一个运算符，所以要定义两个不同的栈，栈1的运算符为字符型；栈2的数字为浮点型，以便运算大数字。再给存储的数据个数加个上制。具体结构定义如下：

#define MAXSIZE 100

typedef struct{

char data[MAXSIZE];              /*字符型，存储运算符*/

int top;

}charSeqStack,*charPSeqStack;

typedef struct{

double data[MAXSIZE];            /*浮点型，存储数字*/

int top;

}SeqStack,*PSeqStack;

4、     功能函数设计

（1）判断操作数的函数isnum()

   判断当前所指字符是否属于数字，是就返回‘1’，不是返回‘0’。

   （2）求运算符优先级函数priority()

为了方便判断运算符优先级，先利用switch函数将不同的运算符返回不同的整型数字，再根据数字的大小判断优先级。‘+’、‘-’优先级相同，返回相同数字，‘*’、‘/’也是。

   （3）表达式求值函数infix_value()

   此函数是直接按照设计思路完成问题要求的函数，其中要调用到判断操作符的函数isnum()和求运算符优先级的函数priority()。循环结束弹出栈2的数值，并返回。

（4）主函数main()

定义一个数组存储表达式整个字符串，将返回的数值直接赋到浮点型的result，输出result。

（5）两个栈的函数设计：

栈的初始化函数charInit_SeqStack()

Init_SeqStack()

         判栈空         Empty_SeqStack()

charEmpty_SeqStack()

入栈函数      Push_SeqStack()

charPush_SeqStack()

出栈函数       Pop_SeqStack()

charPop_SeqStack()

取栈顶函数     GetTop_SeqStack()

                        charGetTop_SeqStack()

销毁栈        Destroy_SeqStack()

charDestroy_SeqStack()

5、     程序代码

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

#define MAXSIZE 100

typedef struct{

    double data[MAXSIZE];

    int top;

}SeqStack,*PSeqStack;

typedef struct{

    char data[MAXSIZE];

    int top;

}charSeqStack,*charPSeqStack;         /*定义栈，两个不同的存储类型*/

PSeqStack Init_SeqStack(void)

{

    PSeqStack S;

    S=(PSeqStack)malloc(sizeof(SeqStack));

    if(S)

       S->top=-1;

    return S;

}

charPSeqStack charInit_SeqStack(void)

{

    charPSeqStack S;

    S=(charPSeqStack)malloc(sizeof(charSeqStack));

    if(S)

       S->top=-1;

    return S;

}                                       /*栈的初始化函数*/

int Empty_SeqStack(PSeqStack S)

{

    if(S->top==-1)

       return 1;

    else

       return 0;

}

int charEmpty_SeqStack(charPSeqStack S)

{

    if(S->top==-1)

       return 1;

    else

       return 0;

}                                          /*判断栈空函数*/

int Push_SeqStack(PSeqStack S,double x)

{

    if(S->top==MAXSIZE-1)

       return 0;

    else

    {

       S->top++;

       S->data[S->top]=x;

       return 1;

    }

}

int charPush_SeqStack(charPSeqStack S,char x)

{

    if(S->top==MAXSIZE-1)

       return 0;

    else

    {

       S->top++;

       S->data[S->top]=x;

       return 1;

    }

}                                            /*入栈函数*/

int Pop_SeqStack(PSeqStack S,double *x)

{

    if(Empty_SeqStack(S))

       return 0;

    else

    {

       *x=S->data[S->top];

       S->top--;

       return 1;

    }

}

int charPop_SeqStack(charPSeqStack S,char *x)

{

    if(charEmpty_SeqStack(S))

       return 0;

    else

    {

       *x=S->data[S->top];

       S->top--;

       return 1;

    }

}                                           /*出栈函数*/

int GetTop_SeqStack(PSeqStack S,double *x)

{

    if(Empty_SeqStack(S))

       return 0;

    else

       *x=S->data[S->top];

    return 1;

}

int charGetTop_SeqStack(charPSeqStack S,char *x)

{

    if(charEmpty_SeqStack(S))

       return 0;

    else

       *x=S->data[S->top];

    return 1;

}                                            /*取栈顶函数*/

void Destroy_SeqStack(PSeqStack *S)

{

    if(*S)

       free(*S);

    *S=NULL;

    return;

}

void charDestroy_SeqStack(charPSeqStack *S)

{

    if(*S)

       free(*S);

    *S=NULL;

    return;

}                                               /*销毁栈*/

int isnum(char c)                     /*判断字符是否为操作符*/

{

    if(c>='0'&&c<='9')

       return 1;

    else

       return 0;

}

int priority(char op)                    /*求运算符的优先级*/

{

    switch(op)

    {

    case'=':return 1;

    case')':return 2;

    case'+':

    case'-':return 3;

    case'*':

    case'/':return 4;

    case'(':return 5;

    default:return 0;

    }

}

double infix_value(char *infix)           /*表达式求值函数，infix为表达式字符串*/

{

    charPSeqStack S1;

    PSeqStack S2;                    /*S1为算符栈，S2为数字栈*/

    char c,w,tope;

    double n,num,m,result,s1,s2;

    S2=Init_SeqStack();

    S1=charInit_SeqStack();             /*初始化栈*/

    if(!S1)

    {

       printf("栈初始化失败");

       return 0;

    }

    if(!S2)

    {

       printf("栈初始化失败");

       return 0;

    }

    charPush_SeqStack(S1,'#');     /*先将‘#’压入算符栈，便于判断结束*/

    w=*infix;                    /*读表达式字符*/

    while((charGetTop_SeqStack(S1,&c),c)!='#'||w!='#')

    {

       num=n=0;

       while(isnum(w))        

       {

           m=w-'0';

           num=num*pow(10,n)+m;  /*求出正确的数字*/

           w=*(++infix);

           n++;                     /*n要不断自加*/

       }

       if(n!=0)Push_SeqStack(S2,num);  /*若读过数字，则将num值压入数字栈*/

       if((charGetTop_SeqStack(S1,&c),c)=='('&&w==')')

       {

           charPop_SeqStack(S1,&tope);

           w=*(++infix);             /*两括号相遇，销毁，读下一个字符*/

       }

       else if((charGetTop_SeqStack(S1,&c),c)=='('||

              priority((charGetTop_SeqStack(S1,&c),c))<priority(w))/*比较运算符*/

       {

           charPush_SeqStack(S1,w);

           w=*(++infix);             

       }

       else

       {

           charPop_SeqStack(S1,&tope);

           Pop_SeqStack(S2,&s2);

           Pop_SeqStack(S2,&s1);

           switch(tope)

              {

                  case'+' : num=s1+s2;break;

                  case'-' : num=s1-s2;break;

                  case'*' : num=s1*s2;break;

                  case'/' : num=s1/s2;break;      /*弹出运算符的同时进行运算*/

              }

              Push_SeqStack(S2,num);       /*将运算结果重新压入栈2*/

       }

    } /*while((charGetTop_SeqStack(S1,&c),c)!='#'||w!='#')*/

    return result;

}

void main()

{

    char number[MAXSIZE];            /*存储表达式*/

    double result;                      /*表达式结果*/

    gets(number);                      /*输入表达式*/

    result=infix_value(number);

    printf("%lf\n",result);                /*输出结果*/

    getch();

}

6、     运行与测试

7、设计心得

   表达式求值是当初老师在教栈这个内容时经常提到的问题，并且也在黑板上演示过，所以在设计思想上基本已经有了框架，写起来也就方便多了，但依然也有些问题不断的出现。首先就是存运算符和数字的问题了，我不知在入栈和出栈时如何能将它们的类型合理的转化，所以只好定义两个栈，以至于这个程序看起来太“啰嗦”。在运行调试时曾遇见一个大问题，程序读不了10以上的数字，很快便找到了问题所在，在功能函数里，它每读一个数字便直接入栈，下一个若是数字便存在栈的下一个地址内了。于是我以while循环控制它何时入栈，将大数计算好了再入栈。在调试过程中还曾遇见了一个问题，就是出栈运算时将两个数字前后弄反了，应该是后出栈的-‘运算符’-前出栈的。

   写完了表达式求值使我又加深了对栈的知识与运用，也让我意识到运用栈时容易出现的错误与改善方法。虽然这个程序运行成功，但整体仍有不足，需要改善，我必须继续深入学习数据结构，以达到可以考虑程序各方面的要求改善程序。

第二篇：数据结构课程设计之表达式求值

学生课程设计

题    目： 表达式求值问题             

      姓名：   赵旺   

学  号：124090102042

所在院(系)：       计算机与信息科学学院                   

专     业：      2012级计算机科学与技术                

班     级：           (2）班                 

指导教师：       冯韵     

20##年9月24日

一．问题描述

要求对包含加、减、乘、除、括号运算符的任意整型表达式进行求解。

二．设计思路

这个程序的关键是对数字与运算符的判断和运算符优先级的判断，以及出栈的运算。建立两个栈，分别存储数字与运算符，栈1存运算符，栈2存数字。依次读取表达式的字符串，先判断是数字还是运算符，如果是数字不能马上压入栈2，因为可能是大于10的数字，应该继续循环，如果还是数字，则利用计算保存数值，直到指到运算符时停止，将计算后的数字压入栈2。压入运算符之前先将要压入的与栈顶的运算符优先级相比较，如果栈顶是‘（’而当前不是‘）’，则不需比较优先级，直接压入；如果栈顶是‘（’，当前是‘）’，则抵消（弹出‘（’，指向表达式下一个字符）；若当前的运算符优先级大于栈顶的，则压入；若当前的运算符优先级小于栈內时，弹出栈顶的运算符，同时弹出两组数字，经过运算符的运算后再重新压到栈内。为了方便判断运算结束，在存储运算符之前先将‘#’压入栈1中，在输入表达式时以“#”结束，所以可以以运算符==‘#’并且栈1顶==‘#’来结束运算，弹出栈2的数值，即为表达式求值的最终结果。

上述操作的算法步骤：

（1） 初始化算符S1,数字栈S2;，将‘#’压入算符栈S1中。

（2） 读表达式字符=>w。

（3） 当栈顶为‘#’并且w也是‘#’时结束；否则循环做下列步骤：

（3-1）如果w是数字，存储到m，再经过计算存储到num中。m=w-‘0’;num=num*pow(10,n)+m;n++;读下一个字符=>w，如果是运算符，则跳出循环；转3-2。

（3-2）w若是运算符，则：

   （3-2-1）如果栈顶为‘（’并且w为‘）’则‘（’出栈，读下一个字符=>w；转（3）。

     （3-2-2）如果栈顶为‘（’或者栈顶优先级小于w优先级，则w入栈，读下一个字符=>w；转（3）。否则：从算符栈中出栈，并从数字栈中弹出两组数字进行运算，将结果重新压入数字栈，转（3）。

2.1数据结构设计

前面提到，要用栈存储数据，由于一个数字一个运算符，所以要定义两个不同的栈，栈1的运算符为字符型；栈2的数字为浮点型，以便运算大数字。再给存储的数据个数加个上制。具体结构定义如下：

#define MAXSIZE 100

typedef struct{

char data[MAXSIZE];              /*字符型，存储运算符*/

int top;

}charSeqStack,*charPSeqStack;

typedef struct{

double data[MAXSIZE];            /*浮点型，存储数字*/

int top;

}SeqStack,*PSeqStack;

2.2功能函数设计

（1）判断操作数的函数isnum()

   判断当前所指字符是否属于数字，是就返回‘1’，不是返回‘0’。

   （2）求运算符优先级函数priority()

为了方便判断运算符优先级，先利用switch函数将不同的运算符返回不同的整型数字，再根据数字的大小判断优先级。‘+’、‘-’优先级相同，返回相同数字，‘*’、‘/’也是。

   （3）表达式求值函数infix_value()

   此函数是直接按照设计思路完成问题要求的函数，其中要调用到判断操作符的函数isnum()和求运算符优先级的函数priority()。循环结束弹出栈2的数值，并返回。

（4） 主函数main()

定义一个数组存储表达式整个字符串，将返回的数值直接赋到浮点型的result，输出result。

（5） 两个栈的函数设计：

栈的初始化函数charInit_SeqStack()

Init_SeqStack()

        判栈空         Empty_SeqStack()

charEmpty_SeqStack()

入栈函数      Push_SeqStack()

charPush_SeqStack()

出栈函数       Pop_SeqStack()

charPop_SeqStack()

取栈顶函数     GetTop_SeqStack()

                        charGetTop_SeqStack()

销毁栈        Destroy_SeqStack()

charDestroy_SeqStack()

三.程序代码

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

#define MAXSIZE 100

typedef struct{

   double data[MAXSIZE];

   int top;

}SeqStack,*PSeqStack;

typedef struct{

   char data[MAXSIZE];

   int top;

}charSeqStack,*charPSeqStack;         /*定义栈，两个不同的存储类型*/

PSeqStack Init_SeqStack(void)

{

   PSeqStack S;

   S=(PSeqStack)malloc(sizeof(SeqStack));

   if(S)

      S->top=-1;

   return S;

}

charPSeqStack charInit_SeqStack(void)

{

   charPSeqStack S;

   S=(charPSeqStack)malloc(sizeof(charSeqStack));

   if(S)

      S->top=-1;

   return S;

}                                       /*栈的初始化函数*/

int Empty_SeqStack(PSeqStack S)

{

   if(S->top==-1)

      return 1;

   else

      return 0;

}

int charEmpty_SeqStack(charPSeqStack S)

{

   if(S->top==-1)

      return 1;

   else

      return 0;

}                                          /*判断栈空函数*/

int Push_SeqStack(PSeqStack S,double x)

{

   if(S->top==MAXSIZE-1)

      return 0;

   else

   {

      S->top++;

      S->data[S->top]=x;

      return 1;

   }

}

int charPush_SeqStack(charPSeqStack S,char x)

{

   if(S->top==MAXSIZE-1)

      return 0;

   else

   {

      S->top++;

      S->data[S->top]=x;

      return 1;

   }

}                                            /*入栈函数*/

int Pop_SeqStack(PSeqStack S,double *x)

{

   if(Empty_SeqStack(S))

      return 0;

   else

   {

      *x=S->data[S->top];

      S->top--;

      return 1;

   }

}

int charPop_SeqStack(charPSeqStack S,char *x)

{

   if(charEmpty_SeqStack(S))

      return 0;

   else

   {

      *x=S->data[S->top];

      S->top--;

      return 1;

   }

}                                           /*出栈函数*/

int GetTop_SeqStack(PSeqStack S,double *x)

{

   if(Empty_SeqStack(S))

      return 0;

   else

      *x=S->data[S->top];

   return 1;

}

int charGetTop_SeqStack(charPSeqStack S,char *x)

{

   if(charEmpty_SeqStack(S))

      return 0;

   else

      *x=S->data[S->top];

   return 1;

}                                            /*取栈顶函数*/

void Destroy_SeqStack(PSeqStack *S)

{

   if(*S)

      free(*S);

   *S=NULL;

   return;

}

void charDestroy_SeqStack(charPSeqStack *S)

{

   if(*S)

      free(*S);

   *S=NULL;

   return;

}                                               /*销毁栈*/

int isnum(char c)                     /*判断字符是否为操作符*/

{

   if(c>='0'&&c<='9')

      return 1;

   else

      return 0;

}

int priority(char op)                    /*求运算符的优先级*/

{

   switch(op)

   {

   case'=':return 1;

   case')':return 2;

   case'+':

   case'-':return 3;

   case'*':

   case'/':return 4;

   case'(':return 5;

   default:return 0;

   }

}

double infix_value(char *infix)           /*表达式求值函数，infix为表达式字符串*/

{

   charPSeqStack S1;

   PSeqStack S2;                    /*S1为算符栈，S2为数字栈*/

   char c,w,tope;

   double n,num,m,result,s1,s2;

   S2=Init_SeqStack();

   S1=charInit_SeqStack();             /*初始化栈*/

   if(!S1)

   {

      printf("栈初始化失败");

      return 0;

   }

   if(!S2)

   {

      printf("栈初始化失败");

      return 0;

   }

   charPush_SeqStack(S1,'#');     /*先将‘#’压入算符栈，便于判断结束*/

   w=*infix;                    /*读表达式字符*/

   while((charGetTop_SeqStack(S1,&c),c)!='#'||w!='#')

   {

      num=n=0;

      while(isnum(w))        

      {

         m=w-'0';

         num=num*pow(10,n)+m;  /*求出正确的数字*/

         w=*(++infix);

         n++;                     /*n要不断自加*/

      }

      if(n!=0)Push_SeqStack(S2,num);  /*若读过数字，则将num值压入数字栈*/

      if((charGetTop_SeqStack(S1,&c),c)=='('&&w==')')

      {

         charPop_SeqStack(S1,&tope);

         w=*(++infix);             /*两括号相遇，销毁，读下一个字符*/

      }

      else if((charGetTop_SeqStack(S1,&c),c)=='('||

            priority((charGetTop_SeqStack(S1,&c),c))<priority(w))/*比较运算符*/

      {

         charPush_SeqStack(S1,w);

         w=*(++infix);             

      }

      else

      {

         charPop_SeqStack(S1,&tope);

         Pop_SeqStack(S2,&s2);

         Pop_SeqStack(S2,&s1);

         switch(tope)

            {

                case'+' : num=s1+s2;break;

                case'-' : num=s1-s2;break;

                case'*' : num=s1*s2;break;

                case'/' : num=s1/s2;break;      /*弹出运算符的同时进行运算*/

            }

            Push_SeqStack(S2,num);       /*将运算结果重新压入栈2*/

      }

   } /*while((charGetTop_SeqStack(S1,&c),c)!='#'||w!='#')*/

   return result;

}

void main()

{

   char number[MAXSIZE];            /*存储表达式*/

   double result;                      /*表达式结果*/

   gets(number);                      /*输入表达式*/

   result=infix_value(number);

   printf("%lf\n",result);                /*输出结果*/

   getch();

}

四.运行与测试

五.设计心得

   表达式求值是当初老师在教栈这个内容时经常提到的问题，并且也在黑板上演示过，所以在设计思想上基本已经有了框架，写起来也就方便多了，但依然也有些问题不断的出现。首先就是存运算符和数字的问题了，我不知在入栈和出栈时如何能将它们的类型合理的转化，所以只好定义两个栈，以至于这个程序看起来太“啰嗦”。在运行调试时曾遇见一个大问题，程序读不了10以上的数字，很快便找到了问题所在，在功能函数里，它每读一个数字便直接入栈，下一个若是数字便存在栈的下一个地址内了。于是我以while循环控制它何时入栈，将大数计算好了再入栈。在调试过程中还曾遇见了一个问题，就是出栈运算时将两个数字前后弄反了，应该是后出栈的-‘运算符’-前出栈的。