南京信息工程大學(xué)濱江學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、濱江學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目 算術(shù)表達(dá)式的求解院系計(jì)算機(jī)系專業(yè)學(xué)生姓名學(xué)號(hào)指導(dǎo)教師李燕二一六年 六 月十日目錄1.前言.11.1課題內(nèi)容及要求 .11.2選題目的及意義 .12.系統(tǒng)分析 .22.1問題描述 .22.2運(yùn)算符的優(yōu)先級(jí)分析： .22.3錯(cuò)誤提示分析： .23.系統(tǒng)概要設(shè)計(jì) .33.1系統(tǒng)總體架構(gòu)設(shè)計(jì) .33.2系統(tǒng)模塊的設(shè)計(jì) .34.系統(tǒng)詳細(xì)設(shè)計(jì) .44.1數(shù)據(jù)的存儲(chǔ)設(shè)計(jì)與描述： .44.2詳細(xì)的優(yōu)先級(jí)關(guān)系 : .44.3具體的操作集合： .45.程序?qū)崿F(xiàn) .66.程序測(cè)試 .136.1正確的結(jié)果 .136.2錯(cuò)誤 1.136.3錯(cuò)誤 2.136.4錯(cuò)誤 3.137.收獲及體會(huì)：

2、 .15I參考文獻(xiàn)：15II1. 前言1.1 課題內(nèi)容及要求題目 39：算術(shù)表達(dá)式的求解問題描述：給定一個(gè)算術(shù)表達(dá)式，通過程序求出最后的結(jié)果?；疽螅簭逆I盤輸入要求解的算術(shù)表達(dá)式；采用棧結(jié)構(gòu)進(jìn)行算術(shù)表達(dá)式的求解過程；能夠判斷算術(shù)表達(dá)式正確與否；對(duì)于錯(cuò)誤表達(dá)式給出提示；對(duì)于正確的表達(dá)式給出最后的結(jié)果；1.2 選題目的及意義進(jìn)一步熟悉和使用棧的基本操作，如棧的初始化，進(jìn)棧，出棧的特性。學(xué)習(xí)在實(shí)際生活中使用棧來解決問題。12. 系統(tǒng)分析2.1 問題描述要正確計(jì)算表達(dá)式的值，必須要正確的解釋表達(dá)式。首先解釋算術(shù)表達(dá)式的運(yùn)算規(guī)則，分為以下三點(diǎn)：先乘除后加減；從左往右進(jìn)行計(jì)算；有括號(hào)的，先算括號(hào)內(nèi)的；2

3、.2 運(yùn)算符的優(yōu)先級(jí)分析：任何一個(gè)表達(dá)式都是由運(yùn)算符，操作數(shù)和界限符組成的。這里把運(yùn)算符，界限符統(tǒng)稱為算符。設(shè)兩個(gè)操作符分別為op1和 op2。為實(shí)現(xiàn)運(yùn)算符的優(yōu)先法則，優(yōu)先關(guān)系會(huì)出現(xiàn)三種情況，op1的優(yōu)先級(jí)高于 op2的優(yōu)先級(jí)， op1的優(yōu)先級(jí)等于 op2的優(yōu)先級(jí)， op1的優(yōu)先級(jí)小于op2的優(yōu)先級(jí)。2.3 錯(cuò)誤提示分析：對(duì)于輸入錯(cuò)誤的，比如出現(xiàn)了表達(dá)式以外的非法字符，沒有按照正確格式進(jìn)行輸入。系統(tǒng)會(huì)給出提示。23. 系統(tǒng)概要設(shè)計(jì)3.1 系統(tǒng)總體架構(gòu)設(shè)計(jì)算術(shù)表達(dá)式的求解棧運(yùn)模算塊模塊定初入出取判判進(jìn)運(yùn)義始棧棧棧斷斷行算?；攦?yōu)是基函的棧的先否本數(shù)結(jié)元級(jí)為運(yùn)構(gòu)素運(yùn)算算函符數(shù)3.2 系統(tǒng)模塊的設(shè)計(jì)

4、為了更好的服務(wù)，結(jié)合用戶的需求，有如下的模塊設(shè)計(jì)：程序主要包括三個(gè)模塊：主函數(shù)設(shè)計(jì)模塊int main()函數(shù)體棧模塊：一些本程序需要的操作，如初始化棧，定義棧，出棧，入棧，取棧頂元素。運(yùn)算模塊：對(duì)一些優(yōu)先級(jí)的定義，以及基本的算術(shù)運(yùn)算。34. 系統(tǒng)詳細(xì)設(shè)計(jì)4.1 數(shù)據(jù)的存儲(chǔ)設(shè)計(jì)與描述：為實(shí)現(xiàn)運(yùn)算符的優(yōu)先算法，可以用兩個(gè)棧：運(yùn)算符棧OPTR，操作數(shù)棧 OPND。四則運(yùn)算表達(dá)式算法的基本思想是：首先置操作數(shù)棧 OPND為空棧，表達(dá)式起始符“ #”為 OPTR棧的棧底元素。依次讀入表達(dá)式中的每個(gè)字符， 是操作數(shù)則進(jìn)棧 OPND，是運(yùn)算符就和 OPTR棧的棧頂元素比較后，依據(jù)相應(yīng)的優(yōu)先權(quán)進(jìn)行操作， 直

5、至整個(gè)表達(dá)式求值完畢 （標(biāo)志是兩個(gè)運(yùn)算符都為 “ #”）。4.2 詳細(xì)的優(yōu)先級(jí)關(guān)系 :Op2+-*/（）#Op1+-*/（#=4.3 具體的操作集合：棧的設(shè)計(jì)：typedef structElemType dataStackSize;int top; SeqStack;void Init(SeqStack *s);/初始化棧int IsFull(SeqStack *s);/判斷棧是否已滿int IsEmpty(SeqStack *s);/判斷棧是否是空void Push(SeqStack *s,ElemType x);/進(jìn)行入棧操棧ElemType Pop(SeqStack *s);/進(jìn)行出棧

6、操作4ElemType getTop(SeqStack *s);/提取棧頂元素函數(shù)運(yùn)算：int Advan(int t1,int t2);/判斷符號(hào)的優(yōu)先級(jí)int In(int c);/判斷 c是否為運(yùn)算符int Oprea(int a,int theta,int b); /進(jìn)行四則運(yùn)算int EvaluteExpression();/進(jìn)行算術(shù)表達(dá)式求值55. 程序?qū)崿F(xiàn)/stack.h中#ifndef _STACK_H#define _STACK_H#define StackSize 100#define MaxLength 100typedef int ElemType;typedef st

7、ructElemType dataStackSize;int top; SeqStack;void Init(SeqStack *s);/初始化棧int IsFull(SeqStack *s);/判斷棧是否已滿int IsEmpty(SeqStack *s);/判斷棧是否是空void Push(SeqStack *s,ElemType x); /進(jìn)行入棧操棧ElemType Pop(SeqStack *s);/進(jìn)行出棧操作ElemType getTop(SeqStack *s); /提取棧頂元素#endif/stack.c中#include stack.h#include #include v

8、oid Init(SeqStack *s)/初始化 ?s-top=-1;int IsFull(SeqStack *s)/判斷棧是否已滿6return s-top=StackSize-1;int IsEmpty(SeqStack *s)/判斷棧是否是空return s-top=-1;void Push(SeqStack *s,ElemType x)/進(jìn)行入棧操棧if(IsFull(s)printf(棧已經(jīng)溢出。 );exit(1);s-top+;/棧頂指針加 1s-datas-top=x;/棧頂為新插入的值，data 是數(shù)組， s-top 數(shù)字ElemType Pop(SeqStack *s)/

9、進(jìn)行出棧操作if(IsEmpty(s)printf(棧是空的 );exit(1);return s-data s-top-;/先刪除棧頂?shù)脑兀缓笾羔槣p一ElemType getTop(SeqStack *s)/提取棧頂元素if(IsEmpty(s)printf(棧是空的 );exit(1);return s-data s-top;7/operstack.h中#ifndef _OPERSTACK_H#define _OPERSTACK-Hint Advan(int t1,int t2);/判斷符號(hào)的優(yōu)先級(jí)int In(int c);/判斷 c是否為運(yùn)算符int Oprea(int a,int

10、 theta,int b);/進(jìn)行四則運(yùn)算int EvaluteExpression();/進(jìn)行算術(shù)表達(dá)式求值#endif/operstack.c中#include stack.h#include #include #include operstack.hint Advan(int t1,int t2)/判斷符號(hào)的優(yōu)先級(jí)int f;switch(t2)case +:/若 t2 符號(hào)是“ +”“ - ”case -:if(t1=(|t1=#)f=;break;case *:/若 t2 符號(hào)是* ， / 時(shí)8case /:if(t1=*|t1=/|t1=)f=;elsef=;break;case

11、(: / 若 t2 符號(hào)是（，此時(shí)應(yīng)該優(yōu)先級(jí)小繼續(xù)輸入，而不進(jìn)行運(yùn)算 if(t1=)printf(ERROR括號(hào)不匹配 n);exit(0);elsef=;break;case #:/若 t2 取出時(shí)是 #，表示已經(jīng)要計(jì)算最后一個(gè)表達(dá)式了switch(t1)case #:f=;break;case (:printf(ERROR缺少右括號(hào) n);exit(0);default:f=;9return f;int In(int c)/判斷 c是否為運(yùn)算符switch(c)case +:case -:case *:case /:case (:case ):case #:return 1;default

12、 :return 0;int Oprea(int a,int theta,int b)/進(jìn)行四則運(yùn)算int c;switch(theta)case +:c=a+b;break;case -:c=a-b;break;case *:c=a*b;break;case /:10c=a/b;break;return c;int EvaluteExpression()/進(jìn)行算術(shù)表達(dá)式求值SeqStack OPTR,OPND;/構(gòu)建兩個(gè)棧，一個(gè)是放操作符，一個(gè)是放數(shù)據(jù)int a,b,d,x,theta;char c;/存放鍵盤接收的字符char z6;/存放整數(shù)串int i;Init(&OPTR);/初始化

13、運(yùn)算符棧Push(&OPTR,#);/#入棧， #是表達(dá)式結(jié)束的標(biāo)志Init(&OPND);/初始化數(shù)據(jù)棧c=getchar();/從鍵盤讀入下一個(gè)字符到cx=getTop(&OPTR);/x賦值為運(yùn)算符棧頂元素while(c!=#|x!=#)/當(dāng)讀入兩個(gè)字符都為#時(shí)，則停止，返回最后的/結(jié)果 X的值，否則繼續(xù)進(jìn)行運(yùn)算if(In(c)/是運(yùn)算符switch(Advan(x,c)case :theta=Pop(&OPTR);/優(yōu)先級(jí)高， 此時(shí)進(jìn)行運(yùn)算 , 從操/ 作棧中取出一個(gè)運(yùn)算符b=Pop(&OPND);/從數(shù)據(jù)棧中取出兩個(gè)數(shù)a=Pop(&OPND);Push(&OPND,Oprea(a,theta,b); /然后通過這兩個(gè)數(shù)進(jìn)行運(yùn)算11else if(c=0&c=0&c=9);zi=0;/整數(shù)串結(jié)束d=atoi(z);/將字符串轉(zhuǎn)化為整數(shù)放入d中Push(&OPND,d);/一個(gè)整數(shù)入到數(shù)據(jù)棧中else/兩者以外顯然不可能，出錯(cuò)printf(ERROR出現(xiàn)了非法的字符，表達(dá)式不符合格式n);exit(0);x=getTop(&OPTR);x=getTop(&OPND);return x;126. 程序測(cè)試6.1 正確的結(jié)果6.2 錯(cuò)誤 16.3 錯(cuò)誤 26.4