C语言课程设计--输入一个表达式,输出其结果

课 程 设 计 报 告

课程名称    C语言程序设计            

课题名称   输入一个表达式，输出其结果 

专    业     通信工程                 

班    级      通信1101               

学    号      27                      

姓    名      皮锋                    

指导教师     罗雅博 彭祯 曹燚         

2012年 6月 29 日

湖南工程学院

课 程 设 计 任 务 书

课程名称  C语言程序设计  

课    题   输入一个表达式，输出其结果  

专业班级     通信1101                  

学生姓名     皮锋                  

学    号     27                  

指导老师     罗雅博 彭祯 曹燚     

审    批                       

任务书下达日期    2012 年 6 月 15 日

任务完成日期    2012 年 6 月 29日

一、设计思想

两种算法首先都要建立两个栈，一个是存放操作数的数栈OdStack，一个是存放运算符的符栈OpStack。数栈采用double型的用来存放浮点数，符栈采用char型的用来存放运算符，由于考虑到运算符有优先级的问题，所以事先做了一个Type用来存储运算符的优先级。栈建立好了之后做栈的相关操作，初始化栈，入栈，出栈，看栈顶。其中入栈要判满，出栈和看栈顶要判空。

中缀转后缀再计算的算法。

此算法的基本思路是先将中缀表达式转换成后缀表达式，之后再利用后缀表达式的算法对表达式进行计算。

首先，用一个char数组将中缀表达式读入，对数组中的每一个元素进行处理，区分哪些是数，哪些是运算符。如果是数元素（或小数点元素），则依次存入用来存储后缀表达式的char数组，直到一个整合数存完之后用空格将其与后面的元素分开。如果是运算符元素，则根据当前运算符的优先级和栈里面的运算符的优先级进行处理。如果栈内元素的优先级小于当前元素的优先级或者栈内为空，则将当前运算符入栈；如果栈内元素的优先级大于等于当前元素的，则依次将出栈元素存入后缀表达式，并用空格将其与后面的元素分开，直到栈内元素的优先级小或者栈内为空。对于左括号来说，无条件进栈，并只在有右括号出现的时候才有可能出栈。对于右括号来说，无条件让栈内元素出栈，直到左括号出栈。依次将每个元素进行处理直到中缀表达式索引完毕。至此，已经实现了将中缀表达式转换成了后缀表达式，在数组的最后加上结束符以便下一步的调用。

第二步，读出后缀表达式并进行计算。如果索引到空格则将索引标志后推1位。之后要先对char型的数字元素进行整合，从后缀表达式中依次取出数字元素（连同小数点）存入一个新的char型数组，直到一整个数取完后通过atof函数将char型转换成浮点型存入数栈，并将新数组初始化用来存储下一个数。如果是索引到运算符，则在数栈中出栈两个数字与当前运算符进行运算，先出栈的数字放在运算符后面，后出栈的数字放在运算符的前面，将运算以后的结果再次存入数栈。依次进行计算直到后缀表达式索引完毕。此时对栈内剩余元素进行操作。每在符栈出栈一个运算符，就从数栈出栈两个数进行计算，算法同上，将运算以后的结果再次存入数栈。循环操作直到符栈栈空，此时数栈出栈元素即为最后结果。

二、算法流程图

中缀转后缀再计算的算法分两个流程，第一步是中缀表达式转换成后缀表达式；

图1 中缀转后缀算法流程图

第二步是将后缀表达式进行计算输出。

三．调试分析过程描述

1.首先，设计的程序每运行一次只能进行一次计算:

int main()

{

    printf("              ******欢迎进入小型计算器******\\n请输入算术表达                式:");

    char str[N];                                     

double result;                                  

    scanf("%s",str);

    result=Calu(str);                      

    printf("输出计算结果: %f\\n",result);

}

为了改进程序，我在主函数里加了一个循环：

int main()

{

    int a;

    printf("              ******欢迎进入小型计算器******\\n    请输入算术表达            式:");

    for(a=0;;a++)

        {

            char str[N];                                         

double result;                                      

            scanf("%s",str);

            result=Calu(str);                            

            printf("输出计算结果: %f\\n",result);

            printf("〉〉");

        }

}

2.为了人性化原则，想什么时候退出计算就退出计算，我对程序又进行了改进，输入字母e退出计算：

if(exp1[index1]=='(')           

    {

        tempsign.Type=exp1[index1];

        tempsign.level=-1;                                                          OpPush(&OpStack,&tempsign);

        index1++;

    }

else

{

        if(exp1[index1]==')')                  

          {

             while(OpPeek(&OpStack).level != -1)                                                  {

                            exp2[index2]=OpPop(&OpStack).Type;

                            index2++;

                            exp2[index2]=' ';                                                            index2++;

                    }

                OpPop(&OpStack);                                                          index1++;

           }

         else if(exp1[index1]=='e')                         /*                            exit(0);

          else

            Error();

}

四．程序运行结果

五．程序源代码

#include

#include

#include

#define N 100                    /*N为数栈和表达式数组容量*/

#define M 100                    /*M为符栈和其他数组容量*/

typedef struct                 /*定义运算符类型，level为运算符等级*/

{

    char Type;                    

    int level;

}Type;                        /*做一个Type用来存储运算符的优先级*/

typedef struct                            /*定义存放操作数的数栈*/

{

    double stack[N];

    int top;

}OdStack;

typedef struct                            /*定义存放运算符的符栈*/

{

    Type stack[M];

    int top;

}OpStack;

void Init_OdStack(OdStack *s)              /*定义初始化数栈*/

{   

    (*s).top=0;  

}                     //初始化栈顶，赋等级0值

void OdPush(OdStack *s,double n)            /*进数栈*/

{

    if((*s).top==N-1)                       /*如果栈满则报错退出程序*/

    Error();

    else

        {

            (*s).stack[(*s ).top]=n;        //将数栈中的值变为n

            (*s).top++;                        //栈顶的值加1

        }

}

double OdPop(OdStack *s)                  /*定义出数栈*/

{

    if ((*s).top==0)                        /*如果栈空则报错退出程序*/

        Error();

    else

        {

            (*s).top--;                            //栈顶的值减1

            return (*s).stack[(*s).top];        //返回数栈中的值

        }

}

void Init_OpStack(OpStack *s)               /*定义初始化符栈*/

{   

    (*s).top=0;  

}                        //初始化栈顶，赋等级0值

void OpPush(OpStack *s,Type *sign)          /*定义进符栈*/

{

    if((*s).top==M-1)                      /*如果栈满则报错退出程序*/

    Error();

    else

    {

        (*s).stack[(*s).top]=*sign;        

        (*s).top++;                        //栈顶的值加1

    }

}

Type OpPop(OpStack *s)                    /*定义出符栈*/

{

    if ((*s).top==0)                        /*栈空则报错退出程序*/

    Error();

    else

        {

            (*s).top--;

            return (*s).stack[(*s).top];        //返回符栈的值

        }

}

Type OpPeek(OpStack *s)                  /*定义看符栈顶*/

{

    Type ren;

    if ((*s).top==0)                        /*判栈空，空则赋等级0值*/

        {

            ren.level=0;        //运算优先级为等级0值            

            return ren;

        }

    else

    return (*s).stack[(*s).top-1];        

}

int Error()                                 /*报错函数*/

{

    printf("输入错误！\\n");

    exit(1);

}

int Com(char tempch)                       /*定义运算符等级*/

{

    int level;                              /*给不同运算符定级*/

    switch (tempch)

        {

            case '+':

            case '-':level=1;break;

            case '*':

            case '/':level=2;break;//乘除优先加减

        }

    return level;                //返回运算符等级

}

double Oper(double a,double b,char tempch)      /*定义运算过程*/

{

    double ren;

    switch (tempch)                   /*对不同运算符执行运算并返回结果*/

        {

            case '+':ren=b+a;break;

            case '-':ren=b-a;break;

            case '*':ren=b*a;break;

            case '/':ren=b/a;break;

         }

    return ren;

}

double Calu(char *exp1)            //

{

    OdStack OdStack;                    /*定义数栈*/

    OpStack OpStack;                     /*定义符栈*/

    Type tempsign;                       /*定义Type型运算符*/

    char exp2[N],tempexp[M],tempch;         /*定义后缀表达式数组exp2，整合数组tempexp，tempch为运算符*/

    int index1,index2,tempindex;            /*index1为主要索引，index2为次要索引，tempindex为附加索引*/

    double number,a,b,c;                    /*number为整合数，a、b、c为运算数*/

    Init_OdStack(&OdStack);               /*初始化数栈*/

    Init_OpStack(&OpStack);               /*初始化符栈*/

    index1=0;                            /*初始化索引，附加索引*/

    index2=0;

    tempindex=0;

    tempexp[0]='\\0';                       /*初始化整合数组*/    

    while(exp1[index1]!='\\0')             /*处理初始表达式转化成后缀表达式*/

      {

        if((exp1[index1]>='0'&& exp1[index1]<='9'))         /*处理数字元素*/

            {

                while((exp1[index1]>='0'&& exp1[index1]<='9') || exp1[index1]=='.' )

                    { 

                        exp2[index2]=exp1[index1];      /*连续的数字元素不分开并依次存入后缀表达式*/

                        index2++;

                        index1++;

                    }

                        exp2[index2]=' ';                    /*结束后用空格将其与后面的元素分开*/

                        index2++;

            }

          else            //不是数字或小数点元素

            { 

                if(exp1[index1]=='+'||exp1[index1]=='-'||exp1[index1]=='*'||exp1[index1]=='/')      //是运算符                                                    /*处理运算符元素*/

                {

                    tempsign.Type=exp1[index1];

                    tempsign.level=Com(tempsign.Type);            /*求运算符等级*/

                    while(OpPeek(&OpStack).level>=tempsign.level)      /*当栈中符的等级大于当前等级时则取出符存入后缀表达式*/

                        {

                            exp2[index2]=OpPop(&OpStack).Type;

                            index2++;

                            exp2[index2]=' ';                   /*每两个运算符之间用空格分开*/

                            index2++;

                        }

                    OpPush(&OpStack,&tempsign);            /*结束后将当前运算符入栈*/

                    index1++;

                }

               else

                {

                    if(exp1[index1]=='(')               /*如果是左括号则无条件进栈*/

                    {

                        tempsign.Type=exp1[index1];

                        tempsign.level=-1;              /*进栈后等级为-1，以便遇到右括号出栈*/

                        OpPush(&OpStack,&tempsign);

                        index1++;

                    }

                   else

                    {

                        if(exp1[index1]==')')                  /*右括号规则*/

                        {

                            while(OpPeek(&OpStack).level != -1)      /*遇到右括号则不断出栈存入后缀表达式直到寻到左括号*/

                            {

                                exp2[index2]=OpPop(&OpStack).Type;

                                index2++;

                                exp2[index2]=' ';        /*每两个运算符之间用空格分开*/

                                index2++;

                            }

                            OpPop(&OpStack);          /*直到遇到左括号将左括号出栈*/

                            index1++;

                        }

                        else if(exp1[index1]=='e')                     

                            exit(0);

                        else                                    /*如果输入了非法字符则报错退出程序*/

                            Error();

                    }

                }

            }

        }

        while(OpPeek(&OpStack).level !=0)         /*原表达式结束后对栈进行操作直到栈空*/

        {

            if(OpPeek(&OpStack).level==-1)          /*如果有为用掉的左括号则报错退出程序*/

            Error();

            exp2[index2]=OpPop(&OpStack).Type;

            index2++;

            exp2[index2]=' ';

            index2++;

        }

        exp2[index2]='\\0' ;                            /*最后结束后缀表达式*/

        index1=0;                                      /*索引归零，开始计算结果*/

        while(exp2[index1] != '\\0')                            /*循环直到后缀表达式结束*/

            {

                if((exp2[index1]>='0'&& exp2[index1]<='9'))          /*整合数并入栈*/

                    {

                        while((exp2[index1]>='0'&& exp2[index1]<='9') || exp2[index1]=='.' )       /*用附加索引判断数的长度并整合入整合数组*/

                            {

                                tempexp[tempindex]=exp2[index1];

                                index1++;

                                tempindex++;

                            }

                            tempexp[tempindex]='\\0';           /*结束整合数组*/

                            if( tempexp[0] != '\\0')                /*如果整合数组有值则转换成浮点型存入数栈*/

                            {

                                  number = atof(tempexp);

                                OdPush(&OdStack ,number);

                                tempexp[0]='\\0';               /*入栈后初始化整合数组和附加索引以便下次整合*/

                                tempindex=0;

                            }

                     }

                    else

                        {

                            if(exp2[index1]==' ')               /*判断空格，有则跳过*/

                            {

                                while(exp2[index1]==' ')

                                index1++;

                            }

                    else

                        {

                            if(exp2[index1]=='+'||exp2[index1]=='-'||exp2[index1]=='*'||exp2[index1]=='/')     /*对加减乘除进行运算*/

                                {

                                    a=OdPop(&OdStack);

                                    b=OdPop(&OdStack);

                                    tempch=(exp2[index1]);

                                    c=Oper(a,b,tempch);

                                    OdPush(&OdStack,c);           /*将计算结果放入数栈*/

                                    index1++;

                                }

                        }

                }

        }

    return OdPop(&OdStack) ;              /*弹出结果*/

}

int main()

{

    int a;

    printf("              ******欢迎进入小型计算器******\\n字母e结输入束计算！\\n请输入算术表达式:");

    for(a=0;;a++)

        {

            char str[N];                             /*定义数组以存储表达式*/

            double result;                             /*定义result以存储结果*/         

            scanf("%s",str);

            result=Calu(str);                          /*计算表达式并返回结果值*/       

            printf("输出计算结果: %f\\n",result);

            printf("〉〉");

        }

}

六．总结

通过对本次程序的学习和编写，了解了关于电脑对计算表达式的计算过程，并且学会了从中缀变成后缀的方法。在本次编写的时候遇到了不少问题和麻烦，通过对C语言的复习和对算法的分析，最终也一一解决。也是这次的编写让我更加认识到算法的重要性和算法的趣味性，特别是中缀转后缀如直接计算的差别体现了算法的发展历程和一个好的算法对于程序的关键性。通过本次编写也意识到了清晰的程序结构对于以后的更新和更改都有很重要的意义，方便的利用函数体来定义一些算法比直接在主函数中设置算法要好的多。更关键的是了解到了栈的性质和用途，一些适当的问题使用栈不仅仅可以迎刃而解，有时还能够起到事倍功半的效果。从栈的构建、定义到入栈、出栈、看栈顶等的操作编写，大幅度提高了个人的编程能力，体会到了不同的结构在程序中所起到的不同的作用。同时也更加关注了程序的容错机制和简介模式。

计算机与通信学院课程设计评分表

设计内容：  C语言程序设计