簡單的四則運算(棧+逆波蘭

1、逆波蘭利用棧實現(xiàn)簡單的四則運算一逆波蘭表達式引自/blog/ 逆波蘭表達式解決四則運算 逆波蘭表達式又叫做后綴表達式，它將復雜表達式轉換為可以依靠簡單的操作得到計算結果的表達式，解決了四則運算中括號改變運算符優(yōu)先級的問題。 四則運算的表達式一般都是中綴表達式如 1+2*(3-4)+5，即操作符在兩個操作數(shù)之間。四則運算需要兩個步驟，一是把中綴表達式轉為后綴表達式，二是由后綴表達生成結果 中綴表達式轉為后綴表達式算法描述： (1)首先有個包含中綴表達式元素列表sourceList,然后創(chuàng)建一個符號列表destList保存最終后綴表達式

2、,創(chuàng)建一個操作符堆棧opStack (2)從sourceList取出一個元素A (3a)如是數(shù)字則加入到destList中 (3b)如果元素A是運算符，將操作符A與操作符堆棧opStack棧頂?shù)倪\算符的優(yōu)先關系相比較。如果，優(yōu)先關系高于opStack棧頂?shù)倪\算符，則將 該運算符壓入操作符堆棧opStack。倘若不是(低于或等于)的話，則將運算符棧opStack棧頂?shù)倪\算符從棧中彈出保存到destList，重復此 步驟,直到作符A壓入操作符堆棧opStack。 (3c)若元素A是左括號(，則壓入操作符堆棧opStack (3d)若元素B是右括號),則操作符堆棧opStack彈出操作符并加入到de

3、stList中，直到彈出左括號(。 (5)從步驟2重復上述操作，所有元素處理完畢后將操作符堆棧opStack彈出操作符并加入到destList中，這樣中綴式表示的簡單算術表達式轉化為逆波蘭表示的簡單算術表達式。 示例： 中綴表達式如 1+2*(3-4)+5，構造元素列表1,+,2,*,(,3,-,4,),5,構造一個空最終后綴表達式destList，一個操作符堆棧opStack 1、取出“1”，destList【1】，opStack【】 2、取出“+”，destList【1】，opStack【+】 3、取出“2”，destList【1,2】，opStack【+】 4、取出“*”，destLis

4、t【1,2】，opStack【+,*】 5、取出“(”，destList【1,2】，opStack【+,*,(】 6、取出“3”，destList【1,2,3】，opStack【+,*,(】 7、取出“-”，destList【1,2,3】，opStack【+,*,(,-】 8、取出“4”，destList【1,2,3,4】，opStack【+,*,(,-】 9、取出“)”，destList【1,2,3,4,-】，opStack【+,*】 /操作符堆棧opStack彈出操作符并加入到destList中，直到彈出左括號( 10、取出“+”，destList【1,2,3,4,-,*,+】，opSta

5、ck【+】 /加號優(yōu)先級不大于【+,*】 11、取出“5”，destList【1,2,3,4,-,*,+,5】，opStack【+】 12、處理完畢，destList【1,2,3,4,-,*,+,5,+】，opStack【】 后綴表達式到計算結果算法描述： 遍歷儲存后綴表達式的列表，將元素依次進棧，當遇到操作符時，連續(xù)出棧兩個元素，進行運算，再將結果進棧，最后棧內留下的元素就是計算結果 示例： 后綴表達式destList【1,2,3,4,-,*,+,5,+】，結果堆棧resultStatck【】 格式 輸入-:結果 1,2,3,4-:resultStatck【1,2,3,4】 -:result

6、Statck【1,2,3-4】 * -:resultStatck【1,2*(3-4)】 +-:resultStatck【1+2*(3-4)】 5-:resultStatck【1+2*(3-4),5】 +-:resultStatck【1+2*(3-4)+5】 舉例：正常的表達式 逆波蘭表達式 a+b - a,b,+ a+(b-c) - a,b,c,-,+ a+(b-c)*d - a,b,c,-,d,*,+ a+d*(b-c) - a,d,b,c,-,*,+ a=1+3 - a=1,3 +二自己寫的簡單四則運算的程序。/逆波蘭利用棧實現(xiàn)簡單的四則運算#include #include #inclu

7、de #include using namespace std; void changebolan(char *sourcelist,char *destlist,int n) stacks; int i=0,j=0; while(sourcelisti!=0) if(isdigit(sourcelisti) destlistj=sourcelisti; i+; j+;/如果是數(shù)字的話直接放到destlist中，然后取sourcelist的下一個符號 else if(sourcelisti=+) | (sourcelisti=-) while(!s.empty() & s.top()!=()/

8、如果是加減號的話，只要不遇到(或者?？盏那闆r下，連續(xù)彈出棧內的符號，因為加減號是優(yōu)先級最低的，不可能大于棧內的符號。 destlistj=s.top();j+;s.pop(); s.push(sourcelisti);/棧內取光了或者遇到了(，壓棧，然后處理sourcelist的下一個符號 i+; if(sourcelisti=*|sourcelisti=/) while(!s.empty()&(s.top()=*|s.top()=/)/如果是乘除的話，遇到乘除就會彈出棧內的，到destlist中，因為等于棧內的，需彈出棧內的， destlistj=s.top();j+;s.pop(); s.

9、push(sourcelisti);/說明遇到了不是乘除的情況，也就是空棧或者(或者加減。此時都需要直接壓棧。然后取出sourcelist的下一個符號 i+; if(sourcelisti=()/如果是(直接壓棧s.push(sourcelisti); i+; if(sourcelisti=) while(s.top()!=()& (!s.empty()/如果是）就將棧內遇到(前的所有元素彈出，到destlist中。 destlistj=s.top();j+;s.pop(); if(!s.empty()s.pop();/將棧內的(刪除，注意不要存進destlist中了、 i+; while(!

10、s.empty() destlistj=s.top(); s.pop(); j+; destlistj=0;int compute(char *destlist,int n) stackT; int i=0; int w=0; while(destlisti!=0) if(isdigit(destlisti)/如果是數(shù)字字符，轉化成int數(shù)字壓棧，然后轉向下一個字符。 w=destlisti-0; T.push(w); i+; else int TF=0,TS=0,m=0;TF=T.top();T.pop(); TS=T.top();T.pop();/取出棧中的前兩個數(shù)據(jù)if(destlisti=+)m=TS+TF; if(destlisti=-)m=TS-TF; if(destlisti=*)m=TS*TF;if(destlisti=/)m=TS/TF;/以上的運算由于棧的原因都是后取出的與前面的做運算。T.push(m);/將兩個數(shù)的計算結果作為一個新的數(shù)壓棧，與棧中的其他數(shù)再運算。然后判斷下一個字符。i+; return T.top();void main() char *sourcelist=new char100; cout請輸入字符串表達式sourcelist; int n=strlen(sourcelist); char *destlist=new charn+1