表達(dá)式翻譯課程設(shè)計報告

1、軟件學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 -表達(dá)式翻譯 指導(dǎo)老師：錢鴿 學(xué) 號： 1415925721專 業(yè)： 云計算班 級：三班姓 名：高笛1. 需求分析 1.1問題描述 在計算機(jī)中，算術(shù)表達(dá)式由常量、變量、運算符和括號組成。由于不同的運算符具有不同的優(yōu)先級，又要考慮括號，因此，算術(shù)表達(dá)式的求值不可能嚴(yán)格地從左到右進(jìn)行。因而在程序設(shè)計時，借助棧實現(xiàn)。 算法輸入：一個算術(shù)表達(dá)式，由常量、變量、運算符和括號組成（以字符串形式輸入）操作符為+、-、*、/，用#表示結(jié)束。 算法輸出：由中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，如果不是括號配對的話則輸出括號不配對。 算法要點：設(shè)置運算符棧和括號配對的棧在進(jìn)行表達(dá)式的譯過程進(jìn)行

2、判斷括號的配對問題。1.2基本要求 設(shè)計友好的用戶界面，利用所學(xué)棧的方法對表達(dá)式的中綴和后綴之間的轉(zhuǎn)換，并且實現(xiàn)對括號配對的判斷。編寫完整程序，將中綴表達(dá)式翻譯成后綴表達(dá)式。表達(dá)式由操作數(shù) ( 變量 ) 、操作 ( 運算符 ) 以及小括弧“（”和“）”組成，其中：1）操作包括算術(shù)運算、關(guān)系運算和邏輯運算三類；2）操作數(shù)為單個字符或由字母和數(shù)字任意多個字符構(gòu)成；3）能夠識別出簡單的錯誤，如括弧不匹配。輸入：中綴表達(dá)式，80個字符以內(nèi)。輸出：運算結(jié)果。2 概要設(shè)計2.1總體功能結(jié)構(gòu)表達(dá)式翻譯是程序設(shè)計語言編譯中的一個最基本的問題。它的實現(xiàn)是棧應(yīng)用的一個典型例子。本程序使用通常使用的算法為“算符優(yōu)先

3、法”。 在計算機(jī)中如果想要計算出一個表達(dá)式的值，則需要先將表達(dá)式轉(zhuǎn)換為計算機(jī)能夠識別的表達(dá)式，即中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式。首先需要了解算數(shù)運算符的優(yōu)先級等。即：1） 先乘除，后加減。2） 從左算到右。3） 先括號內(nèi)，后括號外。故若中綴表達(dá)式為：1*2+(2-(6-4)*4)/2。后綴則為：12*264- 4*-2/+。算符優(yōu)先法就是根據(jù)這個運算優(yōu)先關(guān)系的規(guī)定來實現(xiàn)對表達(dá)式的編譯或解釋執(zhí)行的。2.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計利用一個順序棧可以實現(xiàn)將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，也能實現(xiàn)對括號是否匹配進(jìn)行檢測。通過從鍵盤輸入字符算數(shù)表達(dá)式，經(jīng)運行后由屏幕輸出轉(zhuǎn)化后的后綴表達(dá)式。2.3 程序原理棧（stack）

4、是最常用和最重要的數(shù)據(jù)結(jié)構(gòu)。操作運算符和左括號是放在棧中的，表達(dá)式的優(yōu)先級處理也是基于棧來實現(xiàn)的，通過利用入棧和出棧來調(diào)整運算符的優(yōu)先級。棧是限制在表的一端進(jìn)行插入和刪除的線性表（即一維數(shù)組）。允許插入刪除的一端為棧頂，另一固定端為棧底。當(dāng)表中沒有元素時稱為空棧。如圖2-1所示，棧中有三個元素，進(jìn)棧的順序是a、b、c，當(dāng)需要出棧時其順序為c、b、a。所以棧又稱為后進(jìn)先出的線性表（Last In First Out）,簡稱LIFO表。而在日常生活中，有很多后進(jìn)先出的例子。在程序設(shè)計中，常常需要使得與保存數(shù)據(jù)時相反順序來使用這些數(shù)據(jù)，這時就需要用一個棧來實現(xiàn)。對于棧，常做的基本運算有： （1）棧初

5、始化：Init_Stack(s) c出棧 入棧 圖2-1 a b top 初始條件：棧s不存在 操作結(jié)果：構(gòu)造了一個空棧。 （2）判斷?？眨篍mpty_Stack(s) 初始條件:棧s已存在 操作結(jié)果：若棧s為空棧返回為1，否則返回為0. （3）入棧：Push_Stack(s,x) 初始條件：棧s已存在 操作結(jié)果：在棧s的頂部插入一個新元素x，x成為新的棧頂元素。棧發(fā)生變化。 （4）出棧：Pop_Stack(s) 初始條件：棧s存在且非空 操作結(jié)果：棧s的頂部元素從棧中刪除，棧中少了一個元素。棧發(fā)生變化。 （5）讀棧頂元素：Top_Stack(s) 初始條件：棧s存在且非空 操作結(jié)果：棧頂元素

6、作為結(jié)果返回，棧不變化。棧可以用順序表實現(xiàn)，稱為順序棧；也可以用鏈表實現(xiàn)，稱為鏈棧。順序棧和鏈棧的邏輯功能一樣。順序棧必須先開一定大小的內(nèi)存空間，執(zhí)行起來簡單并且速度快，但可能溢出；鏈棧的內(nèi)存空間隨用隨開，不會溢出；但執(zhí)行復(fù)雜（不斷地動態(tài)分配）且速度慢。3 程序設(shè)計和流程圖3.1程序具體設(shè)計定義一個順序棧類SqStack，首先構(gòu)造一個空棧，包含的操作有進(jìn)棧Push()，出棧Pop()，取棧頂元素GetTop()，判棧的長度StackLen()。利用這個順序棧對中綴表達(dá)式進(jìn)行檢測，若出錯（主要為括號比匹配），給出出錯提示；否則，將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式。判斷表達(dá)式的的正確和如何轉(zhuǎn)換中綴表達(dá)式

7、的過程，共用了兩個棧 s,s1。第一個棧用來將輸入的字符進(jìn)行判斷是否需要進(jìn)行入棧，而第二個棧則是用來存放小括號的，用來判斷括號是否配對的。首先就是對于輸入進(jìn)來的表達(dá)式進(jìn)行過濾數(shù)字，如果是數(shù)字則不進(jìn)棧直接輸出。如果是操作符，先判斷棧是不是空的，是的話直接進(jìn)棧，不是空棧，則需要將棧內(nèi)的元素出棧判斷是哪個操作符，進(jìn)而判斷其優(yōu)先級。在這個過程中有兩個問題： 第一就是棧內(nèi)的操作符與棧外的操作符是同級別的，那么按照從左到右的順序先進(jìn)行棧內(nèi)的操作符運算，再運算棧外的。 第二點如果棧內(nèi)棧外的操作符不同級，要么是大于，要么是小于，當(dāng)是大于的情況下，則直接進(jìn)棧即可，否則需要判斷s棧內(nèi)的頭元素是不是左括號，如果是則

8、說明這個字符在括號內(nèi)，先運算括號內(nèi)的，即直接進(jìn)棧。如果這個字符前面沒有左括號，則將棧內(nèi)出棧的元素輸出。開始3.2流程圖輸入“#”輸出ch輸入chCh為操作數(shù)？是比較優(yōu)先級否輸出退 出4. 源代碼#include<stdio.h>#include<stdlib.h>#define STACK_INIT_SIZE 80#define STACKINCREMENT 10#define MAXBUFFER 10typedef int Status;typedef char ElemType;typedef struct ElemType *base;ElemType *top;

9、int stackSize;sqStack; Status InitStack(sqStack *s)s->base=(ElemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType);if(!s->base) exit(0);s->top=s->base;s->stackSize=STACK_INIT_SIZE;Status Push(sqStack *s,ElemType e)if(s->top - s->base >= s->stackSize)s->base = (ElemType *)r

10、ealloc(s->base,(s->stackSize + STACKINCREMENT)* sizeof(ElemType);if(!s->base) exit(0);s->top=s->base + s->stackSize;s->stackSize=s->stackSize+STACKINCREMENT; *(s->top)=e;s->top+;Status Pop(sqStack *s,ElemType *e)if(s->top = s->base)return;*e= *-(s->top);Status

11、Gettop(sqStack *s)if(s->top = s->base) return ' 'return *(s->top-1);int StackLen(sqStack s)return (s.top-s.base);int main()int j,sign=1; sqStack s,s1;char e,c;InitStack(&s);InitStack(&s1);printf("請輸入中綴表達(dá)式，以#作為結(jié)束標(biāo)志：n");scanf("%c",&c);printf("中綴表達(dá)式

12、轉(zhuǎn)為后綴表達(dá)式為:n");while(c!='#') while(c>='0'&&c<='9')printf("%c",c);scanf("%c",&c);if(c<'0' | c>'9')printf(" ");if(')'=c) if(Gettop(&s1)='(')Pop(&s1,&c);elsesign=0;break;Pop(&

13、;s,&e);while('('!=e)printf("%c ",e);Pop(&s,&e);else if('+'=c | '-'=c )if(!StackLen(s)Push(&s,c);elsedoPop(&s,&e);if('('=e)Push(&s,e);else printf("%c ",e);while(StackLen(s) &&'('!=e);Push(&s,c);else if

14、('*'=c | '/'=c) if(!StackLen(s) Push(&s,c);elsedoPop(&s,&e);if('('=e | '+'=e | '-'=e)Push(&s,e);Push(&s,c);else printf("%c ",e);Push(&s,c);break;while(StackLen(s) &&'('!=e && '+'!=e && &

15、#39;-'!=e);else if('('=c) Push(&s1,c); Push(&s,c);else if('#'=c) break; elseprintf("您輸入有誤！");return -1; if(sign=0) break; else c=getchar(); if(StackLen(s1) /最后查看棧中是否為空 sign=0; while(StackLen(s)Pop(&s,&e);printf("%c ",e); if(sign=0) printf("n But該算術(shù)表達(dá)式圓括號配對錯誤!n"); return 0;5. 課程總結(jié) 通過幾天時間的課程設(shè)計，自己對于數(shù)據(jù)結(jié)構(gòu)才算是真正的入門了。在這個過程中也遇到不少問題，也正是國為這些問題引發(fā)的思考給我?guī)砹耸斋@。從當(dāng)初拿著問題不知從何下手到現(xiàn)在知道如何分析問題，如何用專業(yè)知識解決實際問題的轉(zhuǎn)變。我發(fā)現(xiàn)無論是專業(yè)知識還是動手能力，自己都有很大程度的提高。 在實際上機(jī)操作過