?一,對表達式翻譯的認識:
????????????????????????? 由中綴變后綴,即由標注的算術(shù)表達式變?yōu)橛嬎銠C易識別的式子,并輸出結(jié)果.例:中綴為:? 9+(3-1)*3+10/2?? 變?yōu)楹缶Y:? 9 3 1 – 3 * + 10 2 + /? 計算結(jié)果為: 20
?二 ,轉(zhuǎn)換的主要思想:
第一步:遇到數(shù)字9在后綴表達式中直接輸出,接著是符號”+”入棧 ,
?第二步:第三個字符是“（”，依然是符號，這個時候?qū)⒋朔柸霔?，接著是?shù)字3，直接輸出，然后是符號“-”，這個時候符號仍然入棧
第三步:接下來是數(shù)字1輸出，緊跟著是“）”，此時，我們需要匹配棧里的“（”，然后再匹配前將棧頂數(shù)據(jù)依次出棧：
?第四步:緊接著是符號“*”，直接入棧：
?第五步:遇到數(shù)字3，直接輸出，之后是符號“+”，此時棧頂元素是符號“*”，按照先乘除后加減原理，此時棧頂?shù)某颂杻?yōu)先級比即將入棧的加號要大，所以出棧。而棧中的第二個元素是加號，按照先到先后的原則，這個時候“+”也要出棧。
?第六步:緊接著是數(shù)字10，直接輸出，最后是符號“/”，進棧：
?第七步:最后一個數(shù)字5，這個時候直接輸出5，但是棧里仍然有數(shù)據(jù)，此時可以將棧中符號依次出棧。
三,對后綴表達式的計算:
1. 初始化一個空棧。此桟用來對要運算的數(shù)字進出使用。
2. 后綴表達式中前三個都是數(shù)字，所以9、3、1進棧。
3. 接下來是減號“-”，所以將棧中的1出棧作為減數(shù)，3出棧作為被減數(shù)，并運算3-1得到2，再將2進棧。
4. 接著是數(shù)字3進棧。
5. 后面是乘法“*”，也就意味著棧中3和2出棧，2與3相乘，得到6，并將6進棧。
6. 下面是加法“+”，所以找中6和9出找，9與6相加，得到15，將15進棧。
7. 接著是10與2兩數(shù)字進棧。
8. 接下來是符號因此，棧頂?shù)?/b>2與10出棧，10與2相除，得到5，將5進棧。
9. 最后一個是符號“+”，所以15與5出找并相加，得到20，將20進棧。
10. 結(jié)果是20出棧，棧變?yōu)榭铡?/b>
四,核心代碼
(1)???? 由前綴變后綴:
char* GetBack()//獲取后綴表達式的函數(shù)
{
??? char* middle = new char[30];
??? char* back = new char[30];
??? char* backend = back;
??? InPut(middle);
??? stack s;
??? s.push('#');
??? while (*middle)
??? {
??????? if (Number(*middle) || *middle =='.')//如果是數(shù)字或者小數(shù)的話，直接輸出
??????? {
??????????? *back = *middle;
??????????? back++, middle++;
??????? }
??????? else
??????? {
??????????? if (Number(*(back - 1)))//只有他的上一個時數(shù)字的話，才繼續(xù)給空格
??????????????????????????????????? //否則遇到多個操作符，則輸出域會存在多個空格
??????????? {
??????????????? AddSpace(back);
??????????? }
??????????? if (*middle == ')')//如果右括號的話，輸出所有操作符直到遇到左括號，并拋棄相對應的一堆括號
??????????? {
??????????????? while (s.top() != '(')
?????????????? ?{
??????????????????? *back = s.top();
??????????????????? s.pop();
??????????????????? back++; middle++;
??????????????????? AddSpace(back);
??????????????? }
??????????????? s.pop();//拋棄左括號
??????????? }
??????????? else if (*middle == '(')//遇到左括號，則進入棧
??????????? {
??????????????? s.push(*middle); middle++;
??????????? }
??????????? else if (GetPriority(*middle) >GetPriority(s.top()))//如果棧內(nèi)的操作符優(yōu)先級高于棧外的優(yōu)先級，則入棧
??????????? {
??????????????? s.push(*middle); middle++;
??????????? }
??????????? else if (GetPriority(*middle) <=GetPriority(s.top()))
??????????????????????????????????????????? //如果棧內(nèi)的操作符優(yōu)先級低于或等于棧外的優(yōu)先級，輸出棧內(nèi)的符號，并入棧棧外的符號
??????????? {
??????????????? *back = s.top();
??????????????? s.pop();
??????????????? s.push(*middle);
??????????????? back++; middle++;
??????????????? AddSpace(back);
??????????? }
??????? }
??? }
??? while (s.top() != '#')//中綴表達式遍歷完成，但是=棧中還有符號存在，一一出棧輸出
??? {
??????? AddSpace(back);
??????? *back = s.top();
??????? s.pop(); back++;
??? }
??? *back = '\0';
??? cout << "后綴表達式為: " << backend << endl;
??? return backend;
}
(2)????后綴表達式的計算:
double CountBack(char*back)
{
??? stack s;
??? while (*back)
??? {
??????? if (Number(*back))//遇到數(shù)字
??????? {
??????????? s.push(GetNumber(back));//將正確的數(shù)字入棧
??????? }
??????? else if (*back == ' ')
??????? {
??????????? back++;//遇到空格跳過
??????? }
??????? else
??????? {
??????????? double a = s.top();
??????????? s.pop();
??????????? double b = s.top();
??????????? s.pop();
??????????? s.push(Cauculate(*back, b, a));//遇到符號時，取棧頂?shù)牡诙€數(shù)和第一個數(shù)求解，并入棧
??????????? back++;
??????? }
??? }
??? while (s.size() >= 2)//最終棧內(nèi)存在的數(shù)大于2時，繼續(xù)計算，直到只剩下一個數(shù)
??? {
??????? double a = s.top();
??????? s.pop();
??????? double b = s.top();
??????? s.pop();
??????? s.push(Cauculate(*back, b, a));
??? }
??? //返回這個數(shù)字，既是最終結(jié)果
??? return s.top();
}
