表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)

表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告書(shū)課程題目：表達(dá)式求值問(wèn)題一.需求分析（1）以字符序列的形式從終端輸入語(yǔ)法正確的不含變量的整數(shù)表達(dá)式，將該中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式。（2）實(shí)現(xiàn)對(duì)后綴表達(dá)式的求值。（3）演示在求值過(guò)程中運(yùn)算符棧，操作數(shù)棧，輸入字符和主要操作的變化過(guò)程。二.概要設(shè)計(jì)表達(dá)式求值的算法分為兩步進(jìn)行：首先將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，再求后綴表達(dá)式的值。（1）將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，對(duì)于字符串形式的合法的中綴表達(dá)式，“（”的運(yùn)算優(yōu)先級(jí)最高，“*”次之，“+”，“—”最低，同級(jí)運(yùn)算符從左到右按順序運(yùn)算。轉(zhuǎn)化過(guò)程算法描述如下：從左到右對(duì)中綴表達(dá)式進(jìn)行掃描，每次處理一個(gè)字符。若遇到左括號(hào)入棧。如遇到數(shù)字，原樣輸出。若遇到運(yùn)算符，如果它的優(yōu)先級(jí)比棧頂元素優(yōu)先級(jí)高，則直接入棧，否則棧頂元素出棧，直到新棧頂數(shù)據(jù)元素的優(yōu)先級(jí)比它低，然后將它直接入棧。重復(fù)以上步驟，直到表達(dá)式結(jié)束。若表達(dá)式已全部結(jié)束，將棧頂元素全部出棧。表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共22頁(yè)，當(dāng)前為第1頁(yè)。（2）后綴表達(dá)式求值算法描述如下：從左到右對(duì)后綴表達(dá)式進(jìn)行掃描，每次處理一個(gè)字符。若遇到數(shù)字，轉(zhuǎn)化為整數(shù)，入棧。若遇到運(yùn)算符，出棧兩個(gè)值進(jìn)行運(yùn)算，運(yùn)算結(jié)果再入棧。重復(fù)以上步驟，直到表達(dá)式結(jié)束，棧中最后一個(gè)數(shù)據(jù)元素就是所求表達(dá)式的結(jié)果。表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共22頁(yè)，當(dāng)前為第1頁(yè)。三.詳細(xì)設(shè)計(jì)#include<stdio.h>#include<stdlib.h>#defineTRUE1#defineFALSE0#defineMAXNUM100typedefintDataType;structSeqStack{DataTypes[MAXNUM];intt;};typedefstructSeqStack*PSeqStack;PSeqStackcreateEmptyStack_seq(){PSeqStackpastack;表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共22頁(yè)，當(dāng)前為第2頁(yè)。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;表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共22頁(yè)，當(dāng)前為第3頁(yè)。}}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){/*將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，順利轉(zhuǎn)換返回true，若轉(zhuǎn)換過(guò)程中發(fā)現(xiàn)中綴表達(dá)式非法則返回false*/intstate_int=FALSE;/*state_int記錄狀態(tài)，等于true表示剛讀入的是數(shù)字字符，等于false表示剛讀入的不是數(shù)字字符，設(shè)置這個(gè)變量是為了在每輸出一個(gè)整數(shù)后輸出一個(gè)空格，以免連續(xù)輸出的兩個(gè)整數(shù)混在一起。*/表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共22頁(yè)，當(dāng)前為第4頁(yè)。charc,c2;PSeqStackps=createEmptyStack_seq();/*運(yùn)算符棧*/inti,j=0;if(infix[0]=='\0')returnFALSE;/*不允許出現(xiàn)空表達(dá)式*/for(i=0;infix[i]!='\0';i++){c=infix[i];switch(c){case'':case'\t':case'\n':if(state_int==TRUE)suffix[j++]='';/*狀態(tài)從true轉(zhuǎn)換為false時(shí)輸出一個(gè)空格*/state_int=FALSE;break;/*遇到空格或制表符忽略*/表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共22頁(yè)，當(dāng)前為第5頁(yè)。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;/*遇到數(shù)字輸出*/break;case'(':if(state_int==TRUE)suffix[j++]='';/*狀態(tài)從true轉(zhuǎn)換為false時(shí)輸出一個(gè)空格*/state_int=FALSE;表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共22頁(yè)，當(dāng)前為第6頁(yè)。push_seq(ps,c);/*遇到左括號(hào)，入棧*/break;case')':if(state_int==TRUE)suffix[j++]='';/*狀態(tài)從true轉(zhuǎn)換為false時(shí)輸出一個(gè)空格*/state_int=FALSE;c2=')';while(!isEmptyStack_seq(ps)){c2=top_seq(ps);/*取棧頂*/pop_seq(ps);/*出棧*/if(c2=='('){break;}suffix[j++]=c2;}表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共22頁(yè)，當(dāng)前為第7頁(yè)。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=='/'){表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共22頁(yè)，當(dāng)前為第8頁(yè)。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=='/'){表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共22頁(yè)，當(dāng)前為第9頁(yè)。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);表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共22頁(yè)，當(dāng)前為第10頁(yè)。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;表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共22頁(yè)，當(dāng)前為第11頁(yè)。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':表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共22頁(yè)，當(dāng)前為第12頁(yè)。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'*':表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共22頁(yè)，當(dāng)前為第13頁(yè)。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;表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共22頁(yè)，當(dāng)前為第14頁(yè)。}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;}}表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共22頁(yè)，當(dāng)前為第15頁(yè)。*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()表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共22頁(yè)，當(dāng)前為第16頁(yè)。{charc,infix[MAXNUM],suffix[MAXNUM];intresult;intflag=TRUE;while(flag==TRUE){printf("請(qǐng)輸入表達(dá)式:\nInput:");getline(infix,MAXNUM);if(infixtoSuffix(infix,suffix)==TRUE)printf("suffix:%s\n",suffix);else{printf("輸入有錯(cuò)誤!\n");printf("\nContinue?(y/n)");scanf("%c",&c);if(c=='n'||c=='N')flag=FALSE;while(getchar()!='\n');printf("\n");表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共22頁(yè)，當(dāng)前為第17頁(yè)。continue;}if(calculateSuffix(suffix,&result)==TRUE)printf("Result:%d\n",result);elseprintf("輸入有錯(cuò)誤!\n");printf("\n是否繼續(xù)?(y/n)");scanf("%c",&c);if(c=='n'||c=='N')flag=FALSE;while(getchar()!='\n');printf("\n");}}四.調(diào)試分析(1)用棧的結(jié)構(gòu)來(lái)解決表達(dá)式的求值，首先要解決的問(wèn)題是如何將人們習(xí)慣書(shū)寫(xiě)的中綴表達(dá)式轉(zhuǎn)換成計(jì)算機(jī)容易處理的后綴表達(dá)式。開(kāi)始有些茫然，后來(lái)通過(guò)結(jié)合課本和同學(xué)的幫助完成了該課題。表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共表達(dá)式求值問(wèn)題數(shù)據(jù)結(jié)構(gòu)全文共22頁(yè)，當(dāng)前為第18頁(yè)。(2)對(duì)一些看似簡(jiǎn)單的東西掌握不夠熟練，比如由于函數(shù)的調(diào)用參數(shù)問(wèn)題不熟而造成了調(diào)試的困難。對(duì)于語(yǔ)法的掌握也欠缺成熟，需要進(jìn)一步掌握。（3）棧的結(jié)構(gòu)理解不夠清晰，造成了設(shè)計(jì)程序時(shí)理不清頭緒，需要對(duì)數(shù)據(jù)結(jié)構(gòu)有更深層次的理解。五.過(guò)程演示中綴