banner1.jpg

题目要求
求解形如（a+b)*((c+d)*e+f*h*g)的简单算术表达式的求值问题。这种表达式只包括加、减、乘、除4种运算符。
为了实现表达式求值，可以首先读入原表达式（包括括号）并创建对应二叉树，其次对二叉树进行前序遍历、中序遍历、后续遍历（非递归），并输出逆波兰表达式，最后求解原表达式的值，同时对非法表达式格式能予以判断。
用二叉树的结构来存储表达式，后续遍历二叉树即可得到逆波兰表达式
我的思路

简单说下我的思路吧，网上有一些代码，但是和我这个题目要求有点区别，有的用C++写的，我甚至连头文件都看不懂（这就尴尬了==），然后我之前买的一本数据结构书上有一些思路和参考代码。

  1. 用户输入中缀表达式
  2. 程序将中缀表达式用二叉树的链式存储结构存储下来
  3. 前序、中序遍历这颗二叉树，输出对应的前缀、中缀表达式
  4. 后续遍历（非递归）这颗二叉树，并把遍历结果存储在顺序栈内，并输出后缀表达式
  5. 对后缀表达式进行求值
    （具体分析可以下载我在文底留下的链接，是我的课程设计报告==）
我的代码
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <math.h>
/*定义区*/
#define MAXSIZE 256 
#define length 200
#define ElemType char

int error=0;

 //二叉树的链式存储结构 
 typedef struct BTNode
 {
     ElemType data[length];
     struct BTNode *lchild;
     struct BTNode *rchild;
 }BTNode;



//判断是操作符还是操作数 
int In(char c)
{
if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#') return 1;//操作符

else return 0;//操作数
}     

//判断操作符的优先级 
char Precede(char a,char b)
{
    char r;
    switch(a)
    {
        case '+':
            case '-':if(b=='*'||b=='/'||b=='(') r='<';else r='>';break;  //加减比乘除和左括号的优先级低
            case '*':
                case'/':if(b=='(')r='<';else r='>';break;//乘除比左括号的优先级低
                case'(':if(b==')')//左右括号的优先级相同
                            r='=';
                    else if(b=='#')
                    {
                        printf("表达式错误\n");
                        r='g';
                    }
                    else r='<';//除此之外，左括号比其他符号优先级低
                    break;

                case')':if(b=='(')
                        {
                            printf("表达式错误\n");
                            r='g';
                        }
                        else r='>';//右括号比其他符号优先级高
                        break;
                case'#':if(b==')')
                        {
                            printf("表达式错误\n");
                            r='g';
                        }
                        else if(b=='#')r='=';
                        else r='<'; //#比其他的符号优先级低
                        break;
    }    
    return r;
}    

//将中缀表达式建立一棵二叉树
int ExpBTree(BTNode* &b,char *str)      
{

    int i;
    BTNode *st[MAXSIZE];//节点栈
    BTNode *s;//新建节点指针
    char bt[MAXSIZE];//操作符栈
    char *p;//字符串
    int top1= -1;//操作符栈指针
    int top2= -1;//节点栈指针
    p=str;
    top1++;
    bt[top1]='#'; 
    while(bt[top1]!='#'||*p!='#')//当且仅当操作符栈顶元素为'#'且字符串该位置为'#'时退出循环
    {
        i=0;
        if(In(*p)==0)//字符串该位置是操作数，则直接建立二叉树节点
        {
            s=(BTNode*)malloc(sizeof(BTNode));
            s->lchild=NULL;
            s->rchild=NULL;
            s->data[i]=*p;
            p++;
            i++;
            while(In(*p)==0)
            {
                s->data[i]=*p;
                p++;
                i++;
                if(*p=='.')//如果是a.bc形式，则将a.bc一直存在节点中，直至后面不再是操作数为止
                {
                    s->data[i]=*p;
                    i++;
                    p++;
                    while(In(*p)==0)//当下一个位置是操作符，就存储到节点数组中
                    {
                        s->data[i]=*p;
                        p++;
                        i++;
                    }
                }
            }
            s->data[i]='\0';
            top2++;
            st[top2]=s;//把该节点放入节点栈内
        }    
        else //字符串该位置是操作符，比较该操作符和操作符栈顶元素的优先级
        {

            switch(Precede(bt[top1],*p))
            {
                case '<':
                    top1++;
                    bt[top1]=*p;
                    p++;
                    break;
                    //如果当前操作符优先级 > 栈顶操作符优先级，则让操作符入操作符栈
                case '>':
                    s=(BTNode*)malloc(sizeof(BTNode));
                    s->data[i]=bt[top1];
                    i++;
                    s->data[i]='\0';
                    top1--;
                    s->rchild=st[top2];
                    top2--;
                    s->lchild=st[top2];
                    st[top2]=s;
                    break; 
                    //如果当前操作符优先级 < 栈顶操作符优先级，以操作符栈顶元素建立新的树节点并且取出节点栈顶的两个节点作为该节点的左右孩子节点，并把该节点压入节点栈。
                case '=':
                    top1--;
                    p++;
                    break;
                    //如果当前操作符优先级 = 栈顶操作符优先级，此时，栈顶和当前操作符为左右括号，此时，出栈顶元素，检查字符串中的下一个元素
                case 'g':
                    error=999;
                    goto loop1;
            }     
        }  
              
    }
    loop1:b=st[top2];//树的根节点 
    return 1;
   
}  

//前序遍历得到前缀表达式

char *preexp[MAXSIZE];
int n1=0;
void PreOrder(BTNode *b)
{
    if(b!=NULL)
    {
        preexp[n1]=b->data;
        printf("%s ",b->data);
        n1++;
        PreOrder(b->lchild);
        PreOrder(b->rchild);
    }    
}


//中序遍历得到前缀表达式

char *inexp[MAXSIZE];
int n2=0;
void InOrder(BTNode *b)
{
    if(b!=NULL)
    {
        InOrder(b->lchild);
        inexp[n2]=b->data;
        printf("%s ",b->data);
        n1++;
        InOrder(b->rchild);
    }    
}


 //对二叉树进行后序遍历得到后缀表达书 
 //后序遍历 

char* postexp[MAXSIZE];//存放后缀表达式,每个节点都是一个字符型数组，故这里使用字符型指针数组
int n3=0;

void PostOrder(BTNode *b)
{
    BTNode *St[MAXSIZE];//保存需要返回节点指针
    BTNode *p;
    int flag,top=-1;
    if(b!=NULL)
    {
        do
        {
            while(b!=NULL)
            {

                top++;
                St[top]=b;
                b=b->lchild;
            }
            p=NULL;
            flag=1;
            while(top!=-1 && flag)
            {
                b=St[top];
                if(b->rchild==p)
                {
                    postexp[n3]=b->data;
                    printf("%s ",b->data);
                    n3++;
                    top--;
                    p=b;
                }
                else
                {
                    b=b->rchild;
                    flag=0;
                }

            }
        }while(top!=-1);
            printf("\n");
    }
}



  //后缀表达式求值 
double CompValue()
{
    int r;//字符串的长度
    double St[MAXSIZE];//数栈
    double opnd,opnd1,opnd2;//opnd1,opnd2分别为数栈栈顶的前两个元素，opnd为计算结果
    char ch[length];
    int top=-1;
    int i=0;
    int j;
    double sum;//不能写成int sum，否则当小数点位数过多，会出现错误！
    while (i<n3)
    {
        strcpy(ch,postexp[i]);
        i++;
        if(strcmp(ch,"+")==0)
        {
            opnd1=St[top];top--;
            opnd2=St[top];top--;
            opnd=opnd1+opnd2;
            top++;
            St[top]=opnd;

        }

        else if(strcmp(ch,"-")==0)
        {
            opnd1=St[top];top--;
            opnd2=St[top];top--;
            opnd=opnd2-opnd1;
            top++;
            St[top]=opnd;
        }
        else if(strcmp(ch,"*")==0)
        {
            opnd1=St[top];top--;
            opnd2=St[top];top--;
            opnd=opnd2*opnd1;
            top++;
            St[top]=opnd;
        }
        else if(strcmp(ch,"/")==0)
        {
            opnd1=St[top];top--;
            opnd2=St[top];top--;
            if(opnd1==0)
            {
                printf("不能除以0\n"); 
                error=999;//error为错误变量，以便最后不输出任何结果
                return 0;
            }    
            opnd=opnd2/opnd1;
            top++;
            St[top]=opnd;
        }

        else
        {
            int k;
            int flag=0;//判断是小数还是多位整数、单位整数三种情况
            sum =0;
            r=strlen(ch);
            for(j=0;j<r;j++)
            {
                if(ch[j]=='.')        
                {
                    k=-1;
                    flag=1;
                }
                else 
                    sum=sum*10+(ch[j]-'0');
                k++;
            }
            top++;
            if(flag==0)
                St[top]=sum;

            else    
                St[top]=sum*pow(10,-k);
        //    printf("sum=%");
        //    printf("还原=%f\n",St[top]);

        //    printf("%f\n",St[top]);//这个地方如果用%d，就没办法输出浮点数！！！！

        }

    }
    return St[0];    
}

double ExpValuel(BTNode *b)
{
    printf("后缀表达式：");
    PostOrder(b);
    return (CompValue());
} 

 
int main ()
{
    BTNode *B;//根节点的指针
    double re;//结果变量
    char str[MAXSIZE];//中缀表达式字符串
    printf("*****************************************************\n");
    printf("         这里是计算器程序，包含以下功能\n");
    printf(" 1.支持二目运算符的多位整数、单个整数、小数混合的加减乘除\n");
    printf(" 2.支持对一些简单的非法表达式的判断\n");
    printf(" 3.你可以在任何时候输入leave 退出程序\n");
    printf(" 4.所输入必须是英文符号，以#号键结束！！\n");
    printf("*****************************************************\n");
    printf("                  现在开始！\n");
    while(scanf("%s",str)!=EOF)
    {
        if(strcmp("leave",str)==0)
        {
            printf("程序正确退出！\n");
            break;
        }
        ExpBTree(B,str);//建立二叉树
        if(error!=999)
        {
            printf("前缀表达式：");
            PreOrder(B);
            printf("\n");
            printf("中缀表达式：");
            InOrder(B);
            printf("\n");
            re=ExpValuel(B);//后序遍历并且计算结果
            printf("运算结果：%.2f\n",re);//输出结果保留两位小数
        }
        n1=0;
        n2=0;
        n3=0;
        error=0;
    }
        return 1;
}
我的感受

今天下午，要去答辩，全班同学都得去，本来嘛，我还蛮自足的==（简直愚蠢），因为我的报告写的是整个宿舍页数最多的，20页。然后去了教室，才看见，班里的编程大神（获得了北京市萌芽杯一等奖，我们学校大一好像一共才2 、3个吧），写的报告有40多页，打印出来简直像一本书，你造吗（我们学校周边打印都是单面打印）。
这么厚！
然后我开始慌了
等到大神上去的时候，发现他直接做了一个界面好吗，你懂得，界面，就是软件界面，哎，我甚至都不知道软件界面到底用什么软件可以做？
唉唉唉唉==
散！

我的报告下载(备用)
最后修改：2016 年 10 月 29 日
© 允许规范转载
喜欢我的文章吗？
别忘了点赞或赞赏，让我知道创作的路上有你陪伴。