南京信息工程大學濱江學院數(shù)據(jù)結構課程設計

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

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

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

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

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

6、操作4ElemType getTop(SeqStack *s);/提取棧頂元素函數(shù)運算：int Advan(int t1,int t2);/判斷符號的優(yōu)先級int In(int c);/判斷 c是否為運算符int Oprea(int a,int theta,int b); /進行四則運算int EvaluteExpression();/進行算術表達式求值55. 程序實現(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); /進行入棧操棧ElemType Pop(SeqStack *s);/進行出棧操作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)/進行入棧操棧if(IsFull(s)printf(棧已經(jīng)溢出。 );exit(1);s-top+;/棧頂指針加 1s-datas-top=x;/棧頂為新插入的值，data 是數(shù)組， s-top 數(shù)字ElemType Pop(SeqStack *s)/

9、進行出棧操作if(IsEmpty(s)printf(棧是空的 );exit(1);return s-data s-top-;/先刪除棧頂?shù)脑?，然后指針減一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);/判斷符號的優(yōu)先級int In(int c);/判斷 c是否為運算符int Oprea(int a,int

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

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

12、 :return 0;int Oprea(int a,int theta,int b)/進行四則運算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()/進行算術表達式求值SeqStack OPTR,OPND;/構建兩個棧，一個是放操作符，一個是放數(shù)據(jù)int a,b,d,x,theta;char c;/存放鍵盤接收的字符char z6;/存放整數(shù)串int i;Init(&OPTR);/初始化

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