C語言實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式
本文實(shí)例為大家分享了C語言實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的具體代碼,供大家參考,具體內(nèi)容如下
中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式(思路)
1.創(chuàng)建棧
2.從左向右順序獲取中綴表達(dá)式
a.數(shù)字直接輸出
b.運(yùn)算符
情況一:遇到左括號(hào)直接入棧,遇到右括號(hào)將棧中左括號(hào)之后入棧的運(yùn)算符全部彈棧輸出,同時(shí)左括號(hào)出棧但是不輸出。
情況二:遇到乘號(hào)和除號(hào)直接入棧,直到遇到優(yōu)先級(jí)比它更低的運(yùn)算符,依次彈棧。
情況三:遇到加號(hào)和減號(hào),如果此時(shí)棧空,則直接入棧,否則,將棧中優(yōu)先級(jí)高的運(yùn)算符依次彈棧(注意:加號(hào)和減號(hào)屬于同一個(gè)優(yōu)先級(jí),所以也依次彈棧)直到??栈騽t遇到左括號(hào)為止,停止彈棧。(因?yàn)樽罄ㄌ?hào)要匹配右括號(hào)時(shí)才彈出)。
情況四:獲取完后,將棧中剩余的運(yùn)算符號(hào)依次彈棧輸出
例:比如將:2*(9+6/3-5)+4轉(zhuǎn)化為后綴表達(dá)式 2 9 6 3 / +5 - * 4 +
轉(zhuǎn)換算法代碼如下:
/*中綴轉(zhuǎn)后綴函數(shù)*/ void Change(SqStack *S,Elemtype str[]) { int i=0; Elemtype e; InitStack(S); while(str[i]!='\0') { while(isdigit(str[i])) {/*過濾數(shù)字字符,直接輸出,直到下一位不是數(shù)字字符打印空格跳出循環(huán) */ printf("%c",str[i++]); if(!isdigit(str[i])) { printf(" "); } } /*加減運(yùn)算符優(yōu)先級(jí)最低,如果棧頂元素為空則直接入棧,否則將棧中存儲(chǔ) 的運(yùn)算符全部彈棧,如果遇到左括號(hào)則停止,將彈出的左括號(hào)從新壓棧,因?yàn)樽? 括號(hào)要和又括號(hào)匹配時(shí)彈出,這個(gè)后面單獨(dú)討論。彈出后將優(yōu)先級(jí)低的運(yùn)算符壓入棧中*/ if(str[i]=='+'||str[i]=='-') { if(!StackLength(S)) { PushStack(S,str[i]); } else { do { PopStack(S,&e); if(e=='(') { PushStack(S,e); } else { printf("%c ",e); } }while( StackLength(S) && e != '(' ); PushStack(S,str[i]); } } /*當(dāng)遇到右括號(hào)是,把括號(hào)里剩余的運(yùn)算符彈出,直到匹配到左括號(hào)為止 左括號(hào)只彈出不打?。ㄓ依ㄌ?hào)也不壓棧)*/ else if(str[i]==')') { PopStack(S,&e); while(e!='(') { printf("%c ",e); PopStack(S,&e); } } /*乘、除、左括號(hào)都是優(yōu)先級(jí)高的,直接壓棧*/ else if(str[i]=='*'||str[i]=='/'||str[i]=='(') { PushStack(S,str[i]); } else if(str[i]=='\0') { break; } else { printf("\n輸入格式錯(cuò)誤!\n"); return ; } i++; } /*最后把棧中剩余的運(yùn)算符依次彈棧打印*/ while(StackLength(S)) { PopStack(S,&e); printf("%c ",e); } }
完整代碼如下:
#include<stdio.h> #include<stdlib.h> #include<ctype.h> #include<assert.h> #define INITSIZE 20 #define INCREMENT 10 #define MAXBUFFER 20 #define LEN sizeof(Elemtype) /*棧的動(dòng)態(tài)分配存儲(chǔ)結(jié)構(gòu)*/ typedef char Elemtype; typedef struct{ Elemtype *base; Elemtype *top; int StackSize; }SqStack; /*初始化棧*/ void InitStack(SqStack *S) { S->base=(Elemtype*)malloc(LEN*INITSIZE); assert(S->base !=NULL); S->top=S->base; S->StackSize=INITSIZE; } /*壓棧操作*/ void PushStack(SqStack *S,Elemtype c) { if(S->top - S->base >= S->StackSize) { S->base=(Elemtype*)realloc(S->base,LEN*(S->StackSize+INCREMENT)); assert(S->base !=NULL); S->top =S->base+S->StackSize; S->StackSize+=INCREMENT; } *S->top++ = c; } /*求棧長(zhǎng)*/ int StackLength(SqStack *S) { return (S->top - S->base); } /*彈棧操作*/ int PopStack(SqStack *S,Elemtype *c) { if(!StackLength(S)) { return 0; } *c=*--S->top; return 1; } /*中綴轉(zhuǎn)后綴函數(shù)*/ void Change(SqStack *S,Elemtype str[]) { int i=0; Elemtype e; InitStack(S); while(str[i]!='\0') { while(isdigit(str[i])) {/*過濾數(shù)字字符,直接輸出,直到下一位不是數(shù)字字符打印空格跳出循環(huán) */ printf("%c",str[i++]); if(!isdigit(str[i])) { printf(" "); } } /*加減運(yùn)算符優(yōu)先級(jí)最低,如果棧頂元素為空則直接入棧,否則將棧中存儲(chǔ) 的運(yùn)算符全部彈棧,如果遇到左括號(hào)則停止,將彈出的左括號(hào)從新壓棧,因?yàn)樽? 括號(hào)要和又括號(hào)匹配時(shí)彈出,這個(gè)后面單獨(dú)討論。彈出后將優(yōu)先級(jí)低的運(yùn)算符壓入棧中*/ if(str[i]=='+'||str[i]=='-') { if(!StackLength(S)) { PushStack(S,str[i]); } else { do { PopStack(S,&e); if(e=='(') { PushStack(S,e); } else { printf("%c ",e); } }while( StackLength(S) && e != '(' ); PushStack(S,str[i]); } } /*當(dāng)遇到右括號(hào)是,把括號(hào)里剩余的運(yùn)算符彈出,直到匹配到左括號(hào)為止 左括號(hào)只彈出不打?。ㄓ依ㄌ?hào)也不壓棧)*/ else if(str[i]==')') { PopStack(S,&e); while(e!='(') { printf("%c ",e); PopStack(S,&e); } } /*乘、除、左括號(hào)都是優(yōu)先級(jí)高的,直接壓棧*/ else if(str[i]=='*'||str[i]=='/'||str[i]=='(') { PushStack(S,str[i]); } else if(str[i]=='\0') { break; } else { printf("\n輸入格式錯(cuò)誤!\n"); return ; } i++; } /*最后把棧中剩余的運(yùn)算符依次彈棧打印*/ while(StackLength(S)) { PopStack(S,&e); printf("%c ",e); } } int main() { Elemtype str[MAXBUFFER]; SqStack S; gets(str); Change(&S,str); return 0; }
運(yùn)行效果截圖如下:
如何實(shí)現(xiàn)將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式后計(jì)算值
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
C語言文件操作實(shí)現(xiàn)數(shù)據(jù)持久化(幫你快速了解文件操作函數(shù))
持久數(shù)據(jù)其實(shí)就是將數(shù)據(jù)保存到數(shù)據(jù)庫(kù),下面這篇文章主要給大家介紹了關(guān)于C語言文件操作實(shí)現(xiàn)數(shù)據(jù)持久化(幫你快速了解文件操作函數(shù))的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-11-11C語言數(shù)據(jù)結(jié)構(gòu)與算法之排序總結(jié)(一)
這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu)與算法中的插入類和交換類的各種排序,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2021-12-12VC++中HTControl控件類之CHTRichEdit富文本編輯控件實(shí)例
這篇文章主要介紹了VC++中HTControl控件類之CHTRichEdit富文本編輯控件,是一個(gè)比較實(shí)用的功能,需要的朋友可以參考下2014-08-08C語言深入分析浮點(diǎn)型數(shù)據(jù)存儲(chǔ)
使用編程語言進(jìn)行編程時(shí),需要用到各種變量來存儲(chǔ)各種信息。變量保留的是它所存儲(chǔ)的值的內(nèi)存位置。這意味著,當(dāng)您創(chuàng)建一個(gè)變量時(shí),就會(huì)在內(nèi)存中保留一些空間。您可能需要存儲(chǔ)各種數(shù)據(jù)類型的信息,操作系統(tǒng)會(huì)根據(jù)變量的數(shù)據(jù)類型,來分配內(nèi)存和決定在保留內(nèi)存中存儲(chǔ)什么2022-08-08C++面試基礎(chǔ)之static關(guān)鍵字詳解
這篇文章主要給大家介紹了關(guān)于C++面試基礎(chǔ)之static關(guān)鍵字的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-02-02學(xué)生成績(jī)管理系統(tǒng)C語言代碼實(shí)現(xiàn)
這篇文章主要為大家詳細(xì)介紹了C語言代碼實(shí)現(xiàn)學(xué)生成績(jī)管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-01-01基于MFC實(shí)現(xiàn)單個(gè)文檔的文件讀寫
這篇文章主要為大家詳細(xì)介紹了如何基于MFC實(shí)現(xiàn)單個(gè)文檔的文件讀寫功能,文中的示例代碼講解詳細(xì),對(duì)我們學(xué)習(xí)有一定幫助,感興趣的可以了解一下2022-07-07