


版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
1、11、蛤蟆的數(shù)據(jù)結(jié)構(gòu)筆記之一棧的應(yīng)用之表達式求值實現(xiàn) 本篇名言: “人生不售來回票,一旦動身,絕不能復(fù)返?!?繼續(xù)棧應(yīng)用實現(xiàn),這次是來看下表達式求值的棧實現(xiàn)。1. 表達式求值表達式求值是設(shè)計語言編譯中的一個基本問題,它的實現(xiàn)是棧應(yīng)用的又一個典型例子。任何一個表達式都是由操作數(shù)(Operand)、運算符(operator)和界限符(delimiter)組成。操作數(shù)可以是常數(shù)也可以是變量或變量的標(biāo)識符。運算符可以分為算術(shù)運算符、關(guān)系運算符和邏輯運算符三類。界限符有左右括號和表達式結(jié)束符。幾個算術(shù)四則運算的規(guī)則:先乘除,后加減;從左算到右先括號內(nèi),后括號外此處實現(xiàn),假定不出現(xiàn)語法錯誤,否則過于復(fù)雜,
2、蛤蟆也不能理解了。2. 運算符優(yōu)先級對于連個相繼出現(xiàn)的操作符0 1和0 2有三種關(guān)系:大于、等于和小于。由此可以列出之間的優(yōu)先級。如卜表:+ -* / ()#+ > >< < <>>- > >< < <>>* > >> > <>>/ > >> > <>>( < << < <=) > >> >>># < << < <=加減乘除優(yōu)先性都低
3、于 “(”但是高于“”,由運算從左到右可知,當(dāng) 0仁蔦 令0 1>02 為了算法簡潔,在表達式的左邊和右邊虛設(shè)一個“ #”這一對“ #表示一個表達式求值完成?!埃ā?)“”當(dāng)一對括號相遇時表示括號內(nèi)已運算完成。)”和“(”、“ #和 “、“和“ #無法相繼出現(xiàn)如果出現(xiàn)則表達式出現(xiàn)語法錯誤。為實現(xiàn)優(yōu)先算法,可以使用兩個工作棧,一個是OPTR用于寄存運算符,一個是OPND,用于寄存運算數(shù)和運算結(jié)果。3. 算法基本思路首先置操作數(shù)棧為空棧,表達式起始符為“ #為棧底元素。依次讀入表達式中的每個字符,若是操作數(shù)則進 OPND棧,若是運算符則和 OPTR棧的 棧頂運算符比較優(yōu)先權(quán)作相應(yīng)操作,直至整
4、個表達式求值完畢(OPTR棧頂元素和當(dāng)前讀入的字符均為“#”'。4. 求值函數(shù) EvaluateExpressio實現(xiàn)根據(jù)算法基本思路,代碼實現(xiàn)如下:int EvaluateExpressio n()int flag;char c;char x,theta;char a,b);In itStack(&OPTR);Push(&OPTR,'#');In itStack(&OPND);flag=getNext (&c);GetTop(OPTR, &x);while(c匸'#' | x != '#')if(
5、flag = 0)flag = getNext(&c);itch(Precede(x, c)case'v':/棧頂元素優(yōu)先級低Pop(&OPND,&b);Pop(&OPND,& a);Push(&OPND, Operate®, theta, b)GetTop(OPTR, &x);GetTop(OPND, &c); freestack(&OPTR); freestack(&OPND); return c;5. Main函數(shù)實現(xiàn)Main函數(shù)實現(xiàn)void mai n()int c;pr in t
6、f( "Please in put one expressi on:"c=EvaluateExpressi on();printf( "Result=%dn" ,c);結(jié)果如下圖1所示:旳 rWindow5syst-eirn32cnnrd.eKe0=1 &l( SJPlease Inirut ons expression :1 *2*3+4/2#Result =9革按耳意型謖F6.源碼可以直接在VS上進行編譯運行。#include "stdio.h"#include "stdlib.h"#include &
7、quot;ctype.h"typedef int Status;#define STACK_INIT_SIZE100#define STACKINCREMENT10typedef char SElemType;/*放入堆棧的元素的類型*/ typedef structSElemType *base;SElemType *top;int stacksizeSqStack;判斷是否為空棧StatusStackEmpty(SqStackS)if (S.top = S.base)return 1;elsereturn 0;用e返回S的頂元素StatusGetTop(SqStackS, SEl
8、emType *e)if (S.top = S.base)return -1;*e = *(S.top-1);return 1;插入e為新的頂元素StatusPushSqStack *S, SEIemType e)if (S->top - S->base) >= S>stacksize)S->base =(SElemType*)realloc( S->base (S>stacksize+STACKINCREMENT )* sizeof(SElemType) );if(! S->base)exit(-1);S->top = S->bas
9、e +S->stacksize;S->stacksize += STACKINCREMENT ;return 1;/刪除S的頂元素,并用e返回其值StatusPop(SqStack *S, SEIemType *e)if (S->top = S->base)return -1;S->top-;*e = *( S->top);return 1;從棧底到棧頂依次對S的每個元素調(diào)用函數(shù)Visit (), 旦失敗操作無效Status ListTraverse( SqStackS,Status (* visit)(SEIemType)SEIemType *p;p=S.
10、base;for(p=S.base;p<S.top;p+)(*visit)(*p);輸出元素eStatusoutput(SElemType e)printf( "%d " ,e);return 1/*計算整數(shù)表達式的值/*判斷輸入的某個字符是否是運算符*c表示輸入的字符Statusi n(char c,char op)char *p;p=op;while (*p != '0')if(c = *p)*op數(shù)組中存放系統(tǒng)能識別的運算符return 1;P+;return 0;/case'#': j=6; break;-/*進行實際的運算*a
11、, b中分別以整數(shù)的形式存放兩個待運算的操作數(shù) theta中存放代表操作符的字符比較兩個運算符的優(yōu)先級*a,b中存放待比較的運算符*'>'表示 a>b*'0'表示不可能出現(xiàn)的比較*/char Precedehara, char b)int i,j;char pre7=/*運算符之間的優(yōu)先級制作成一張表格*/'>' '>' '<''<' '<' '>' '>''v','v
12、9;,'v','v','v','=','O','>','>','>','>','0','>','>','v','v','v','v','v','0','=';switch (a)case'+': i=0; break;case'-
13、9;: i=1; break;case'*': i=2; break;case'/': i=3; break case'(': i=4; break;case')': i=5; break;case'#': i=6; break;switch (bcase'+': j=0; break;case'-': j=1; break;case'*': j=2; break;case'/': j=3; break;case'(': j=4; br
14、eak;case')': j=5; break;*結(jié)果以整數(shù)的形式返回*/int Operate (nt a, char theta, int b) int “result;case'*': result = i * j; break; case'/': result = i / j; break;retur n result;/*從輸入緩沖區(qū)中獲得下一個整數(shù)或運算符,并通過n帶回到主調(diào)函數(shù)*返回值為1表示獲得的是運算符*返回值為0表示獲得的是整形操作數(shù)*/nt getNext(char *n)char c;*n=0;while (c=getch
15、ar()=' );/*跳過一個或多個空格 */if (!isdigit(c)/*通過函數(shù)判斷如果字符不是數(shù)字,那么只能是運算符*/n=c;do/*能執(zhí)行到該條語句,說明字符是數(shù)字,此處用循環(huán)獲得連續(xù)的數(shù)字*/* n=* n*10+(c- '0');/*把連續(xù)的數(shù)字字符轉(zhuǎn)換成相對應(yīng)的整數(shù)*/c=getchar(); while(isdigit(c);/*如果下一個字符是數(shù)字,進入下一輪循環(huán)*/un getc(c,stdi n);/*新讀入的字符不是數(shù)字,可能是運算符,為了不影響下次讀入,把該字符放回到輸入緩沖區(qū)*/return 0;intEvaluateExpressi on()char a,bGetTop(OPTR, &x);while(c匸'#' | x != '#')if(flag = 0)Push(&OPND,c); flag = getNext(&c);elseGetTop(OPTR, &x); switch(Precede(x, c)case'v':/棧頂元素優(yōu)先級低Push(&OPTR,c);flag = getNext(&c);break;case'-':/脫括號并接受下一字符Pop(&OPT
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 明確職業(yè)目標(biāo)的成長路徑計劃
- 生活與事業(yè)雙豐收的秘籍計劃
- 2025年發(fā)動機基本件:飛輪項目發(fā)展計劃
- 2025年血液凈化產(chǎn)品項目建議書
- 2025年工藝品及其他制造產(chǎn)品項目發(fā)展計劃
- 2025年包裝材料加工機械項目建議書
- 2025年運動捕捉軟件合作協(xié)議書
- 2025年包裝印刷機械項目合作計劃書
- 2025年工業(yè)清洗清理設(shè)備:工業(yè)吸塵設(shè)備項目發(fā)展計劃
- 跨區(qū)域業(yè)務(wù)數(shù)據(jù)轉(zhuǎn)換協(xié)調(diào)機制
- 學(xué)生獎勵兌換券模板
- 手術(shù)室醫(yī)院感染控制規(guī)范
- 鑄牢中華民族共同體意識主題班會教案
- 運營與管理行業(yè)培訓(xùn)資料
- 48貴州省貴陽市2023-2024學(xué)年五年級上學(xué)期期末數(shù)學(xué)試卷
- 騎手食品安全培訓(xùn)
- 血液透析誘導(dǎo)期健康宣教
- 第十六章二次根式單元復(fù)習(xí)題-2023-2024學(xué)年人教版八年級數(shù)學(xué)下冊
- 2023-2024新版北師大七年級數(shù)學(xué)下冊全冊教案
- 風(fēng)電場升壓站培訓(xùn)課件
- 2024年光大環(huán)保(中國)有限公司招聘筆試參考題庫含答案解析
評論
0/150
提交評論