數(shù)據(jù)結(jié)構(gòu)之中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式

1、精選優(yōu)質(zhì)文檔-傾情為你奉上我們?cè)跀?shù)學(xué)中常見的計(jì)算式，例如2+（3*4）叫做中綴表達(dá)式。表達(dá)式中涉及到了多個(gè)運(yùn)算符，而運(yùn)算符之間是有優(yōu)先級(jí)的。計(jì)算機(jī)在計(jì)算并且處理這種表達(dá)式時(shí)，需要將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，然后再進(jìn)行計(jì)算。中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式遵循以下原則：1.遇到操作數(shù)，直接輸出；2.棧為空時(shí)，遇到運(yùn)算符，入棧；3.遇到左括號(hào)，將其入棧；4.遇到右括號(hào)，執(zhí)行出棧操作，并將出棧的元素輸出，直到彈出棧的是左括號(hào)，左括號(hào)不輸出；5.遇到其他運(yùn)算符+-*/時(shí)，彈出所有優(yōu)先級(jí)大于或等于該運(yùn)算符的棧頂元素，然后將該運(yùn)算符入棧；6.最終將棧中的元素依次出棧，輸出。經(jīng)過上面的步驟，得到的輸出既是轉(zhuǎn)換得到的

2、后綴表達(dá)式。舉例：a+b*c+(d*e+f)*g - abc*+de*f+g*+遇到a，直接輸出：遇到+，此時(shí)棧為空，入棧：遇到b，直接輸出：遇到*,優(yōu)先級(jí)大于棧頂符號(hào)優(yōu)先級(jí)，入棧：遇到c，輸出：遇到+，目前站內(nèi)的*與+優(yōu)先級(jí)都大于或等于它，因此將棧內(nèi)的*，+依次彈出并且輸出，并且將遇到的這個(gè)+入棧：遇到(,將其入棧：遇到d，直接輸出：遇到*，由于*的優(yōu)先級(jí)高于處在棧中的(，因此*入棧：遇到e，直接輸出：遇到+，棧頂?shù)?優(yōu)先級(jí)高于+，但是棧內(nèi)的(低于+，將*出棧輸出，+入棧：遇到f，直接輸出：遇到),彈出棧頂元素并且輸出，直到彈出(才結(jié)束，在這里也就是彈出+輸出，彈出(不輸出：遇到*，優(yōu)先級(jí)高

3、于棧頂+，將*入棧：遇到g，直接輸出：此時(shí)已經(jīng)沒有新的字符了，依次出棧并輸出操作直到棧為空：明白了這個(gè)過程，現(xiàn)在就需要用代碼實(shí)現(xiàn)了。對(duì)于各種運(yùn)算符的優(yōu)先級(jí)，可以使用整數(shù)來表示運(yùn)算符的級(jí)別。可以定義一個(gè)函數(shù)來返回各種符號(hào)的優(yōu)先級(jí)數(shù)字：/*根據(jù)字符該字符是否在棧中，返回該字符的優(yōu)先級(jí)。*這里只處理+、-、*、/、(、)這些符號(hào)。*需要注意的是：如果(在棧中，它的優(yōu)先級(jí)是最低的，不在棧中則是最高的*param c:需要判斷的字符*param flag:字符是否在棧中，0表示在棧中，1表示不在棧中*/int GetPrecedence(char c,int flag)if(c=+ | c=-)retu

4、rn 1;else if(c=* | c=/)return 2;else if(c=( & flag=0)return 0;else if(c=( & flag=1)return 3;elsefprintf(stderr,Input char is invalid!n);return -1;/*判斷一個(gè)字符是不是運(yùn)算符*如果是合法的運(yùn)算符+、-、*、/、(、)則返回0，否則返回1*/int IsOperator(char c)if(c=+|c=-|c=*|c=/|c=(|c=)return 0;elsereturn 1;/*完整的代碼如下：*/#include #include #define

5、 ElementType chartypedef struct Node *PtrToNode;typedef PtrToNode Stack;typedef struct NodeElementType Element;PtrToNode Next;int IsEmpty(Stack S);Stack CreateStack();void DisposeStack(Stack S);void MakeEmpty(Stack S);void Push(ElementType X,Stack S);ElementType Top(Stack S);void Pop(Stack S);/判斷棧是否

6、為空int IsEmpty(Stack S)return S-Next = NULL;/創(chuàng)建鏈棧Stack CreateStack()Stack S = malloc(sizeof(struct Node);if(S = NULL)printf(No enough memory!);return NULL;S-Next = NULL;MakeEmpty(S);return S;/清空棧void MakeEmpty(Stack S)if(S = NULL)printf(Use CreateStack First!);elsewhile(!IsEmpty(S)Pop(S);/進(jìn)棧void Push

7、(ElementType X,Stack S)PtrToNode Tmp;Tmp = malloc(sizeof(struct Node);if(Tmp != NULL)Tmp-Element = X;Tmp-Next = S-Next;S-Next = Tmp;elseprintf(Out of space!);/出棧void Pop(Stack S)if(IsEmpty(S)printf(The Stack is Empty!);elsePtrToNode Tmp = S-Next;S-Next = Tmp-Next;free(Tmp);/返回棧頂元素ElementType Top(Sta

8、ck S)if(IsEmpty(S)printf(The stack is empty!);return 0;elsereturn S-Next-Element;/*根據(jù)字符該字符是否在棧中，返回該字符的優(yōu)先級(jí)。*這里只處理+、-、*、/、(、)這些符號(hào)。*需要注意的是：如果(在棧中，它的優(yōu)先級(jí)是最低的，不在棧中則是最高的*param c:需要判斷的字符*param flag:字符是否在棧中，0表示在棧中，1表示不在棧中*/int GetPrecedence(char c,int flag)if(c=+ | c=-)return 1;else if(c=* | c=/)return 2;els

9、e if(c=( & flag=0)return 0;else if(c=( & flag=1)return 3;elsefprintf(stderr,Input char is invalid!n);return -1;/*判斷一個(gè)字符是不是運(yùn)算符*如果是合法的運(yùn)算符+、-、*、/、(、)則返回0，否則返回1*/int IsOperator(char c)if(c=+|c=-|c=*|c=/|c=(|c=)return 0;elsereturn 1;char Output50;/中綴表達(dá)式轉(zhuǎn)成后綴表達(dá)式char* InfixToPostfix(char *ch,Stack S)int ind

10、ex=0;char c;while(c=*ch) != 0)/不是運(yùn)算符，將該字符放進(jìn)輸出字符數(shù)組中。if(IsOperator(c)=1)Outputindex+ = c;ch+;/是運(yùn)算符else/如果此時(shí)棧為空，運(yùn)算符進(jìn)棧if(IsEmpty(S)Push(c,S);ch+;continue;elseif(c=)while(!IsEmpty(S) & Top(S) != ()Outputindex+ = Top(S);Pop(S);Pop(S);ch+;continue;elseint outPrecedence = GetPrecedence(c,1);while(!IsEmpty(S) & GetPrecedence(Top(S),0) = outPrecedence)Outputindex+ = Top(S);Pop(S);Push(c,S);ch+;continue;while(!IsEmpty(S)Outputindex+ = Top(S);Pop(S);Outputindex = 0;return Output;int main(void)Stack S = Cr