表達(dá)式翻譯數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

1、數(shù)據(jù)結(jié)構(gòu)課程考核報告 表達(dá)式的翻譯學(xué)號： 1515925640 姓名： 王伊慶 專業(yè)： 軟件工程專業(yè) 班級： 15級云計算1班 指導(dǎo)教師： 錢 鴿 南 陽 理 工 學(xué) 院 軟 件 學(xué) 院2016年12月 目錄1.需求分析-3 1.1問題描述-3 1.2基本要求-32.系統(tǒng)設(shè)計-33.程序流程圖-44.類關(guān)系圖-65. 實現(xiàn)代碼-76.個人總結(jié)-77.參考書目-7一需求分析 1.1問題描述 編寫完整程序，將中綴表達(dá)式翻譯成后綴表達(dá)式。表達(dá)式由操作數(shù) ( 變量 ) 、操作 ( 運算符 ) 以及小括弧 “ （ ” 和 “ ） ” 組成，其中：(1)操作包括算術(shù)運算、關(guān)系運算和邏輯運算三類；(2)操作

2、數(shù)為單個字符或由字母和數(shù)字任意多個字符構(gòu)成；(3)能夠識別出簡單的錯誤，如括弧不匹配。 1.2 基本要求 輸入：中綴表達(dá)式，80個字符以內(nèi)。 輸出：運算結(jié)果 功能：將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式 二系統(tǒng)設(shè)計 根據(jù)題目要求，將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式。問題的解決方案有兩種，分別是利用棧結(jié)構(gòu)實現(xiàn)算數(shù)表達(dá)式的四則運算或者利用二叉樹把中綴表達(dá)式轉(zhuǎn)化為前綴表達(dá)式，我選擇棧結(jié)構(gòu)與樹結(jié)構(gòu)相結(jié)合來實現(xiàn)算數(shù)表達(dá)式的轉(zhuǎn)化。算法思想：運用棧和隊列來將中綴轉(zhuǎn)換為后綴，棧用來儲存字符，隊列用來存儲后綴表達(dá)式。：輸入字符串c，若是數(shù)字的話直接進(jìn)入隊列，若是符號，為*/（，則線檢查棧中的棧頂元素，前提是棧不為空，若棧不為空

3、的話，棧頂元素為*|/，則先將棧中的元素入隊，如果棧頂是+-這些優(yōu)先級小的，則直接將c入棧。：如果c是優(yōu)先級為“+”“-”的字符，先看一下棧是否為空，接著判斷棧頂元素是否為“（”，若是，則繼續(xù)將c進(jìn)棧，否則的話，將棧中的元素全部出棧，直到棧空。：若c為“）”則將棧中所有符號彈棧并進(jìn)入隊列。：若c為“#”，則結(jié)束，并將棧中的剩余的符號全部入隊列。：打印隊列中的，出隊打印。 開始3 程序流程圖輸入一個字符串celse ifC!=#Ifc!=.|c0If(!c!=.|c0)若為數(shù)存入數(shù)組,i=1else if將數(shù)組中第0個存到隊列中If(c*|c=/|c=()else ifIf(c+|c=-)If(

4、c=)If?？諚ｍ敵鰲＝oc2while棧空棧頂出棧給eelse ifIf(c2=*|c2=/)棧頂出棧入隊操作If(e!=()棧頂出棧入隊操作棧頂元素出棧c2進(jìn)棧后c進(jìn)棧c2進(jìn)隊列c入棧else ife=(else ifwhile?？誩=#入棧棧中剩余的出棧入隊操作結(jié)束4 類關(guān)系圖(1) .頭文件：#include#include(2)宏定義：#define OK 1#define ERROR 0#define STACK_SIZE 20#define STACK_INCREMENT 10#define QUEUE_SIZE 20(3) 棧的定義結(jié)構(gòu)體typedef int Status;ty

5、pedef char StackElemtype; /棧的類型typedef struct Stack StackElemtype* base; StackElemtype* top; int stackSize;Stack;(5)初始化棧：Status StackInit(Stack* s)(6)出棧：Status Pop(Stack* s,StackElemtype* value)(7)進(jìn)棧：Status Push(Stack* s,StackElemtype value)(8)求棧的長度：int StackLength(Stack s)(9)定義隊列的結(jié)構(gòu)體：typedef double

6、 QueueElemtype;typedef char QueueOperatorValue;typedef struct QueueNode /定義隊列結(jié)構(gòu)體 QueueElemtype data; QueueOperatorValue operator; struct QueueNode* next; int flag;QueueNode,*QueueNodePtr;typedef struct Queue QueueNodePtr front; QueueNodePtr rear;Queue;(10)初始化隊列Status QueueInit(Queue* q)(11)隊列的插入：Sta

7、tus QueueInsert(Queue* q,QueueElemtype value)(12)出隊列Status QueueInsert_operatorValue(Queue* q,QueueOperatorValue value)(13)中綴轉(zhuǎn)后綴函數(shù)Status Infix2Postfix(Queue* q)(14)打印后綴表達(dá)式Status ShowQueue(Queue q)(15)主函數(shù)int main() Queue q; QueueInit(&q); Infix2Postfix(&q); ShowQueue(q); return 0;5 運行截圖六實現(xiàn)代碼#include#

8、include#define OK 1#define ERROR 0#define STACK_SIZE 20#define STACK_INCREMENT 10#define QUEUE_SIZE 20typedef int Status;typedef char StackElemtype; /棧的類型typedef struct Stack StackElemtype* base; StackElemtype* top; int stackSize;Stack;Status StackInit(Stack* s) /初始化棧 s-base = (StackElemtype*)malloc

9、(sizeof(StackElemtype) * STACK_SIZE); /申請棧的空間 if( !s-base ) return ERROR; s-top = s-base; s-stackSize = STACK_SIZE; return OK;Status Pop(Stack* s,StackElemtype* value) /出棧操作 if( s-base = s-top ) printf(nstack emptyn); return ERROR; *value = *(-(s-top); return OK;Status Push(Stack* s,StackElemtype va

10、lue) /進(jìn)棧操作 if( s-top - s-base = s-stackSize) s-base = (StackElemtype*)realloc(s-base,sizeof(StackElemtype) * (STACK_INCREMENT + STACK_SIZE); if( !s-base ) return ERROR; s-top = s-base + STACK_SIZE; s-stackSize = STACK_SIZE + STACK_INCREMENT; *(s-top) = value; s-top+; return OK;int StackLength(Stack

11、s) /求棧的長度 return s.top - s.base;typedef double QueueElemtype;typedef char QueueOperatorValue;typedef struct QueueNode /定義隊列結(jié)構(gòu)體 QueueElemtype data; QueueOperatorValue operator; struct QueueNode* next; int flag;QueueNode,*QueueNodePtr;typedef struct Queue QueueNodePtr front; QueueNodePtr rear;Queue;St

12、atus QueueInit(Queue* q) /隊列初始化 q-front = (QueueNodePtr)malloc(sizeof(QueueNode); if( !q-front ) return ERROR; q-rear = q-front; q-rear-next = NULL; return OK;Status QueueInsert(Queue* q,QueueElemtype value) /隊列插入 QueueNodePtr new; new = (QueueNodePtr)malloc(sizeof(QueueNode); if( !new ) return ERRO

13、R; new-data = value; new-flag = 1; new-next = NULL; q-rear-next = new; q-rear = new; return OK;Status QueueInsert_operatorValue(Queue* q,QueueOperatorValue value) QueueNodePtr new; new = (QueueNodePtr)malloc(sizeof(QueueNode); if( !new ) return ERROR; new-operator = value; new-flag = 0; new-next = N

14、ULL; q-rear-next = new; q-rear = new; return OK;/利用棧將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式：Status Infix2Postfix(Queue* q) Stack s; StackInit(&s); char c,e; char bufferDigit10; int i = 0; double longDigit; printf(n); printf(n); printf(n); printf( n); printf(n); printf( * 請輸入表達(dá)式 *n); printf( * 結(jié)束符號為# *n); scanf(%c, &c); whil

15、e( # != c) while( c = 0 | . = c ) bufferDigiti+ = c; bufferDigiti = 0; scanf(%c, &c); if(!(c = 0 ) | . = c ) longDigit = atof(bufferDigit); QueueInsert(q,longDigit); i = 0; if( ( = c | * = c | / = c ) if(c=/|c=*) Pop(&s, &e); if(e=/|e=*) QueueInsert_operatorValue(q, e); if(e=+|e=-) Push(&s,e); Push(

16、&s, c); else if( + = c | - = c ) if( !StackLength(s) ) Push(&s, c); else Pop(&s, &e); while( ( != e ) QueueInsert_operatorValue(q, e); if( StackLength(s) = 0 ) break; else Pop(&s, &e); if( ( = e ) Push(&s, e); Push(&s, c); else if( ) = c ) Pop(&s, &e); while( ( != e ) QueueInsert_operatorValue(q, e)

17、; Pop(&s, &e); else if( # = c) break; else printf(input ERROR!n); return ERROR; scanf(%c, &c); while(StackLength(s) Pop(&s, &e); QueueInsert_operatorValue(q, e); QueueInsert_operatorValue(q,#); return OK;Status ShowQueue(Queue q) printf(The Reverse Polish Notation is:); if(q.front = q.rear) printf(Q

18、ueue Empty); return ERROR; QueueNodePtr p = q.front-next; while(p != q.rear) if(p-flag) printf(%g , p-data); else printf(%c , p-operator); p = p-next; printf(n); return OK;int main() Queue q; QueueInit(&q); Infix2Postfix(&q); ShowQueue(q); return 0;7. 個人總結(jié)這個課程設(shè)計為期一周，在每一次的課程設(shè)計都給我很大的收獲，至少是能徹底的把思想給明白，首先，在寫這個課程設(shè)計之前，一直都