表达式求值问题数据结构

表达式求值问题数据结构《数据结构》课程设计报告书课程题目：表达式求值问题一.需求分析（1）以字符序列的形式从终端输入语法正确的不含变量的整数表达式，将该中缀表达式转换为后缀表达式。（2）实现对后缀表达式的求值。（3）演示在求值过程中运算符栈，操作数栈，输入字符和主要操作的变化过程。二.概要设计表达式求值的算法分为两步进行：首先将中缀表达式转换为后缀表达式，再求后缀表达式的值。（1）将中缀表达式转换为后缀表达式，对于字符串形式的合法的中缀表达式，“（”的运算优先级最高，“*”次之，“+”，“—”最低，同级运算符从左到右按顺序运算。转化过程算法描述如下：从左到右对中缀表达式进行扫描，每次处理一个字符。若遇到左括号入栈。如遇到数字，原样输出。若遇到运算符，如果它的优先级比栈顶元素优先级高，则直接入栈，否则栈顶元素出栈，直到新栈顶数据元素的优先级比它低，然后将它直接入栈。重复以上步骤，直到表达式结束。若表达式已全部结束，将栈顶元素全部出栈。表达式求值问题数据结构全文共22页，当前为第1页。（2）后缀表达式求值算法描述如下：从左到右对后缀表达式进行扫描，每次处理一个字符。若遇到数字，转化为整数，入栈。若遇到运算符，出栈两个值进行运算，运算结果再入栈。重复以上步骤，直到表达式结束，栈中最后一个数据元素就是所求表达式的结果。表达式求值问题数据结构全文共22页，当前为第1页。三.详细设计#include<stdio.h>#include<stdlib.h>#defineTRUE1#defineFALSE0#defineMAXNUM100typedefintDataType;structSeqStack{DataTypes[MAXNUM];intt;};typedefstructSeqStack*PSeqStack;PSeqStackcreateEmptyStack_seq(){PSeqStackpastack;表达式求值问题数据结构全文共表达式求值问题数据结构全文共22页，当前为第2页。pastack=(PSeqStack)malloc(sizeof(structSeqStack));if(pastack==NULL)printf("Outofspace!!\n");elsepastack->t=-1;returnpastack;}intisEmptyStack_seq(PSeqStackpastack){returnpastack->t==-1;}voidpush_seq(PSeqStackpastack,DataTypex){if(pastack->t>=MAXNUM-1)printf("Overflow!\n");else{pastack->t=pastack->t+1;pastack->s[pastack->t]=x;表达式求值问题数据结构全文共表达式求值问题数据结构全文共22页，当前为第3页。}}voidpop_seq(PSeqStackpastack){if(pastack->t==-1)printf("Underflow!\n");elsepastack->t=pastack->t-1;}DataTypetop_seq(PSeqStackpastack){returnpastack->s[pastack->t];}intinfixtoSuffix(constchar*infix,char*suffix){/*将中缀表达式转换为后缀表达式，顺利转换返回true，若转换过程中发现中缀表达式非法则返回false*/intstate_int=FALSE;/*state_int记录状态，等于true表示刚读入的是数字字符，等于false表示刚读入的不是数字字符，设置这个变量是为了在每输出一个整数后输出一个空格，以免连续输出的两个整数混在一起。*/表达式求值问题数据结构全文共表达式求值问题数据结构全文共22页，当前为第4页。charc,c2;PSeqStackps=createEmptyStack_seq();/*运算符栈*/inti,j=0;if(infix[0]=='\0')returnFALSE;/*不允许出现空表达式*/for(i=0;infix[i]!='\0';i++){c=infix[i];switch(c){case'':case'\t':case'\n':if(state_int==TRUE)suffix[j++]='';/*状态从true转换为false时输出一个空格*/state_int=FALSE;break;/*遇到空格或制表符忽略*/表达式求值问题数据结构全文共表达式求值问题数据结构全文共22页，当前为第5页。case'0':case'1':case'2':case'3':case'4':case'5':case'6':case'7':case'8':case'9':state_int=TRUE;suffix[j++]=c;/*遇到数字输出*/break;case'(':if(state_int==TRUE)suffix[j++]='';/*状态从true转换为false时输出一个空格*/state_int=FALSE;表达式求值问题数据结构全文共表达式求值问题数据结构全文共22页，当前为第6页。push_seq(ps,c);/*遇到左括号，入栈*/break;case')':if(state_int==TRUE)suffix[j++]='';/*状态从true转换为false时输出一个空格*/state_int=FALSE;c2=')';while(!isEmptyStack_seq(ps)){c2=top_seq(ps);/*取栈顶*/pop_seq(ps);/*出栈*/if(c2=='('){break;}suffix[j++]=c2;}表达式求值问题数据结构全文共表达式求值问题数据结构全文共22页，当前为第7页。if(c2!='('){free(ps);suffix[j++]='\0';returnFALSE;}break;case'+':case'-':if(state_int==TRUE)suffix[j++]='';state_int=FALSE;while(!isEmptyStack_seq(ps)){c2=top_seq(ps);if(c2=='+'||c2=='-'||c2=='*'||c2=='/'){表达式求值问题数据结构全文共表达式求值问题数据结构全文共22页，当前为第8页。pop_seq(ps);suffix[j++]=c2;}elseif(c2=='(')break;}push_seq(ps,c);break;case'*':case'/':if(state_int==TRUE)suffix[j++]='';state_int=FALSE;while(!isEmptyStack_seq(ps)){c2=top_seq(ps);if(c2=='*'||c2=='/'){表达式求值问题数据结构全文共表达式求值问题数据结构全文共22页，当前为第9页。pop_seq(ps);suffix[j++]=c2;}elseif(c2=='+'||c2=='-'||c2=='(')break;}push_seq(ps,c);break;default:free(ps);suffix[j++]='\0';returnFALSE;}}if(state_int==TRUE)suffix[j++]='';while(!isEmptyStack_seq(ps)){c2=top_seq(ps);表达式求值问题数据结构全文共表达式求值问题数据结构全文共22页，当前为第10页。pop_seq(ps);if(c2=='('){free(ps);suffix[j++]='\0';returnFALSE;}suffix[j++]=c2;}free(ps);suffix[j++]='\0';returnTRUE;}intcalculateSuffix(constchar*suffix,int*presult){intstate_int=FALSE;PSeqStackps=createEmptyStack_seq();intnum=0,num1,num2;表达式求值问题数据结构全文共表达式求值问题数据结构全文共22页，当前为第11页。inti;charc;for(i=0;suffix[i]!='\0';i++){c=suffix[i];switch(c){case'0':case'1':case'2':case'3':case'4':case'5':case'6':case'7':case'8':case'9':表达式求值问题数据结构全文共表达式求值问题数据结构全文共22页，当前为第12页。if(state_int==TRUE)num=num*10+c-'0';elsenum=c-'0';state_int=TRUE;break;case'':case'\t':case'\n':if(state_int==TRUE){push_seq(ps,num);state_int=FALSE;}break;case'+':case'-':case'*':表达式求值问题数据结构全文共表达式求值问题数据结构全文共22页，当前为第13页。case'/':if(state_int==TRUE){push_seq(ps,num);state_int=FALSE;}if(isEmptyStack_seq(ps)){free(ps);returnFALSE;}num2=top_seq(ps);pop_seq(ps);if(isEmptyStack_seq(ps)){free(ps);returnFALSE;表达式求值问题数据结构全文共表达式求值问题数据结构全文共22页，当前为第14页。}num1=top_seq(ps);pop_seq(ps);if(c=='+')push_seq(ps,num1+num2);if(c=='-')push_seq(ps,num1-num2);if(c=='*')push_seq(ps,num1*num2);if(c=='/')push_seq(ps,num1/num2);break;default:free(ps);returnFALSE;}}表达式求值问题数据结构全文共表达式求值问题数据结构全文共22页，当前为第15页。*presult=top_seq(ps);pop_seq(ps);if(!isEmptyStack_seq(ps)){free(ps);returnFALSE;}free(ps);returnTRUE;}voidgetline(char*line,intlimit){charc;inti=0;while(i<limit-1&&(c=getchar())!=EOF&&c!='\n')line[i++]=c;line[i]='\0';}voidmain()表达式求值问题数据结构全文共表达式求值问题数据结构全文共22页，当前为第16页。{charc,infix[MAXNUM],suffix[MAXNUM];intresult;intflag=TRUE;while(flag==TRUE){printf("请输入表达式:\nInput:");getline(infix,MAXNUM);if(infixtoSuffix(infix,suffix)==TRUE)printf("suffix:%s\n",suffix);else{printf("输入有错误!\n");printf("\nContinue?(y/n)");scanf("%c",&c);if(c=='n'||c=='N')flag=FALSE;while(getchar()!='\n');printf("\n");表达式求值问题数据结构全文共表达式求值问题数据结构全文共22页，当前为第17页。continue;}if(calculateSuffix(suffix,&result)==TRUE)printf("Result:%d\n",result);elseprintf("输入有错误!\n");printf("\n是否继续?(y/n)");scanf("%c",&c);if(c=='n'||c=='N')flag=FALSE;while(getchar()!='\n');printf("\n");}}四.调试分析(1)用栈的结构来解决表达式的求值，首先要解决的问题是如何将人们习惯书写的中缀表达式转换成计算机容易处理的后缀表达式。开始有些茫然，后来通过结合课本和同学的帮助完成了该课题。表达式求值问题数据结构全文共表达式求值问题数据结构全文共22页，当前为第18页。(2)对一些看似简单的东西掌握不够熟练，比如由于函数的调用参数问题不熟而造成了调试的困难。对于语法的掌握也欠缺成熟，需要进一步掌握。（3）栈的结构理解不够清晰，造成了设计程序时理不清头绪，需要对数据结构有更深层次的理解。五.过程演示中缀