生活随笔
收集整理的這篇文章主要介紹了
四则运算表达式求值（栈的应用）
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
1.前/中/后綴表達(dá)式的轉(zhuǎn)換（首先需要明白三者之間的轉(zhuǎn)換）??
???自然表達(dá)式轉(zhuǎn)換為前/中/后綴表達(dá)式，其實是很簡單的。首先將自然表達(dá)式按照優(yōu)先級順序，構(gòu)造出與表達(dá)式相對應(yīng)的二叉樹，然后對二叉樹進(jìn)行前/中/后綴遍歷，即得到前/中/后綴表達(dá)式。
??? 舉例說明將自然表達(dá)式轉(zhuǎn)換成二叉樹：
??? a×(b+c)-d
??? ① 根據(jù)表達(dá)式的優(yōu)先級順序，首先計算(b+c)，形成二叉樹
???
???
???②然后是a×(b+c)，在寫時注意左右的位置關(guān)系
???
???③最后在右邊加上?-d
???
??? 然后最這個構(gòu)造好的二叉樹進(jìn)行遍歷，三種遍歷的順序分別是這樣的：
??? ① 前序遍歷：根-左-右
???②?中序遍歷：左-根-右
???③?后序遍歷：左-右-根
??? 所以還是以剛才的這個例子，在最終二叉樹的基礎(chǔ)上可以得出：
??? 前綴表達(dá)式：-*a+bcd
??? 中綴表達(dá)式：a*b+c-d
??? 后綴表達(dá)式：abc+*d-
2.中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式（棧的應(yīng)用）??
?中綴表達(dá)式“9+（3-1）*3+10/2”轉(zhuǎn)化為后綴表達(dá)式為“9 3 1- 3 * + 10 2 / +”.
?? 規(guī)則：從左到右遍歷中綴表達(dá)式的每一數(shù)字和符號，若是數(shù)字就輸出，即成為后綴表達(dá)式的一部分；若是符號，則判斷其與棧? 頂符號的優(yōu)先級，是右括號或優(yōu)先級低于棧頂符號（乘除優(yōu)先加減）則棧頂元素依次出棧并輸出，并將當(dāng)前符號進(jìn)棧，一直到最終輸出后綴表達(dá)式為止。
??? a.初始化一空棧，用來對符號進(jìn)出棧使用。
??? b.第一個字符是數(shù)字9，輸出9，后面是符號“+”，進(jìn)棧。
??? c.第三個字符是“（”，依然是符號，因其只是左括號，還沒有配對，故進(jìn)棧。
??? d.第四個字符是數(shù)字3，輸出，總表達(dá)式為9 3，接著是“-”，進(jìn)棧。
??? e.接下來是數(shù)字1，輸出，總表達(dá)式為9 3 1，后面是符號“）”，此時，我們需要去匹配此前的“（”，所以棧頂依次出棧，并輸出，直到“（”出棧為止。此時左括號上方只有“-”，因此輸出“-”。總的表達(dá)式為9 3 1 -。
??? f.接著是數(shù)字3，輸出，總的表達(dá)式為9 3 1 - 3.緊接著是符號“*”，因為此時的棧頂符號為“+”號，優(yōu)先級低于“*”，因此不輸出，“*”進(jìn)棧。
??? g.之后是符號“+”，此時當(dāng)前棧頂元素“*”比這個“+”的優(yōu)先級高，因此棧中元素出棧并輸出（沒有比“+”更低的優(yōu)先級，所以全部出棧），總輸出表達(dá)式為9 3 1 - 3 * +。然后將當(dāng)前這個符號“+”進(jìn)棧。
??? h.緊接著數(shù)字10，輸出，總表達(dá)式為9 3 1 - 3 * + 10。后是符號“/”，所以“/”進(jìn)棧。
??? i.最后一個數(shù)字2，輸出，總的表達(dá)式為9 3 1 - 3 * + 10 2。
??? j.因已經(jīng)到最后，所以將棧中符號全部出棧并輸出。最終輸出的后綴表達(dá)式結(jié)果為9 3 1 - 3 * + 10 2 / +。
3.后綴表達(dá)式計算結(jié)果（棧的應(yīng)用）
???后綴表達(dá)式為：9 3 1 - 3 * + 10 2 / +
?? 規(guī)則為：從左到右遍歷表達(dá)式的每個數(shù)字和符號，遇到是數(shù)字就進(jìn)棧，遇到是符號，就將處于棧頂兩個數(shù)字出棧，進(jìn)行運算，運算結(jié)果進(jìn)棧，一直到最終獲得結(jié)果。
?? a.初始化一個空棧。此棧用來對要運算的數(shù)字進(jìn)行進(jìn)出使用。
?? b.后綴表達(dá)式中前三個是、都是數(shù)字，所以9 3 1 進(jìn)棧。
?? c.接下來是“-”，所以將棧中的1出棧作為減數(shù)，3出棧作為被減數(shù)，并運算3-1得到2，再講2進(jìn)棧。
?? d.接著是數(shù)字3進(jìn)棧。
?? e.后面是“*”，也就意味著棧中3和2出棧，2與3相乘，得到6，并將6進(jìn)棧。
?? f.下面是“+”，所以棧中6和9出棧，9和6相加，得到15，將15進(jìn)棧。
?? g.接著是10和2兩數(shù)字進(jìn)棧。
?? h.接下來是符號“/”，因此，棧頂?shù)?與10出棧，10與2相除，得到5，將5進(jìn)棧。
?? i.最后一個是符號“+”，所以15與5出棧并相加，得到20，講20進(jìn)棧。
?? j.結(jié)果是20出棧，棧變?yōu)榭铡?/span>
?
?
[cpp]?view plaincopy
?? ?? #include<iostream>?? #include<cstdio>?? #include<string>?? #include<stack>?? using?namespace?std;?? ?? stack<char>?s;??? stack<int>?ss;??? ?? int?main()?? {?? ????int?len1,?len2,?len,?i,?j;?? ????string?str1,?str2;?? ????while?(1){?? ???????????? ??????????getline(cin,?str1);?? ??????????len1?=?str1.length();?? ??????????str2.clear();??? ??????????for?(i?=?0;?i?<?len1;?i++){?? ??????????????if?(str1[i]?>=?'0'?&&?str1[i]?<=?'9')??? ?????????????????str2.push_back(str1[i]);?? ??????????????else{?? ???????????????????if?(s.size()?==?0?||?str1[i]?==?'(')?? ???????????????????????s.push(str1[i]);?? ???????????????????else{?? ????????????????????????char?tmp1?=?s.top();?? ????????????????????????if?(str1[i]?==?')'){?? ????????????????????????????len?=?s.size();??? ???????????????????????????while?(len){?? ?????????????????????????????????char?tmp?=?s.top();??? ????????????????????????????????s.pop();?? ????????????????????????????????if?(tmp?==?'(')?? ????????????????????????????????????break;?? ????????????????????????????????else??? ????????????????????????????????????str2.push_back(tmp);??? ????????????????????????????????len--;??? ????????????????????????????}??? ????????????????????????}??? ????????????????????????else{?? ?????????????????????????????if?(tmp1?==?'*'?||?tmp1?==?'/'){?? ?????????????????????????????????if?(str1[i]?==?'*'?||?str1[i]?==?'/')??? ?????????????????????????????????????s.push(str1[i]);?? ?????????????????????????????????else{?? ??????????????????????????????????????len?=?s.size();??? ??????????????????????????????????????while?(len){?? ??????????????????????????????????????????char?tmp?=?s.top();??? ??????????????????????????????????????????str2.push_back(tmp);?? ??????????????????????????????????????????s.pop();??? ??????????????????????????????????????????len--;??? ??????????????????????????????????????}?? ??????????????????????????????????????s.push(str1[i]);???? ?????????????????????????????????}??? ?????????????????????????????}??? ?????????????????????????????else{?? ??????????????????????????????????s.push(str1[i]);??? ?????????????????????????????}??? ????????????????????????}??? ???????????????????}???? ??????????????}??? ??????????}?? ??????????if?(s.size()?!=?0){?? ??????????????len?=?s.size();??? ??????????????while?(len){?? ??????????????????char?tmp?=?s.top();??? ??????????????????str2.push_back(tmp);?? ??????????????????s.pop();??? ??????????????????len--;??? ??????????????}??? ??????????}??? ??????????cout?<<?str2?<<?endl;?? ???????????? ??????????int?temp1,?temp2,?temp3;??? ??????????len2?=?str2.length();?? ??????????for?(i?=?0;?i?<?len2;?i++){?? ??????????????if?(str2[i]?>=?'0'?&&?str2[i]?<=?'9'){??? ??????????????????int?t?=?str2[i]-48;??? ??????????????????ss.push(t);??? ??????????????}??? ??????????????else{?? ???????????????????temp1?=?ss.top();?? ???????????????????ss.pop();?? ???????????????????temp2?=?ss.top();?? ???????????????????ss.pop();??? ???????????????????if?(str2[i]?==?'+'){?? ???????????????????????temp3?=?temp2?+?temp1;??? ???????????????????}?? ???????????????????else?if?(str2[i]?==?'-'){?? ????????????????????????temp3?=?temp2?-?temp1;??? ???????????????????}?? ???????????????????else?if?(str2[i]?==?'*'){?? ????????????????????????temp3?=?temp2?*?temp1;??? ???????????????????}?? ???????????????????else?if?(str2[i]?==?'/'){?? ????????????????????????temp3?=?temp2?/?temp1;??? ???????????????????}?? ???????????????????ss.push(temp3);??? ??????????????}?? ??????????}?? ??????????cout?<<?ss.top()?<<?endl;??? ????}??? ?????? ????system("pause");?? } ?
總結(jié)
以上是生活随笔為你收集整理的四则运算表达式求值（栈的应用）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
