摘要：來實驗室已經兩周了，用師兄的話說，基本處于自嗨狀态。張老師問C++學的怎麼樣了？能不能編一個簡單的電腦出來？我想這個電腦肯定不能簡單到隻算加減乘除，于是想來想去想寫一個能處理括号的電腦，最好能寫個簡單的UI出來。在思考過程中發現，這個電腦的難點就是如何把中綴表達式轉換為字尾表達式，以及如何計算字尾表達式。
計算思路
人的思路
如果隻是用于解題的話，這種方法是最快最準确的。但是它不适用于計算機。下面以a+b*c+(d*e+f)*g為例子講以下人應該怎麼把中綴表達式轉換成字尾表達式。
按先加減後乘除的原則給表達式加括号
結果：((a+(b*c))+(((d*e)+f)*g))
由内到外把每個括号裡的表達式換成字尾
最終結果：abc*+de*f+g*+
這樣就得到了中綴表達式轉字尾表達式的最終結果。此法應付考試有神效。
計算機的思路
畢竟計算機跟人不一樣，它“笨”啊！人的思路它用不了。那麼它該怎麼把中綴表達式轉換成字尾表達式呢？
計算機的思路需要用到棧，先來明确中綴表達式轉字尾表達式的規則：
1)如果遇到操作數，我們就直接将其輸出。
2)如果遇到操作符，則我們将其放入到棧中，遇到左括号時我們也将其放入棧中。
3)如果遇到一個右括号，則将棧元素彈出，将彈出的操作符輸出直到遇到左括号為止。注意，左括号隻彈出并不輸出。
4)如果遇到任何其他的操作符，如(“+”， “”，“(”)*等，從棧中彈出元素直到遇到發現更低優先級的元素(或者棧為空)為止。彈出完這些元素後，才将遇到的操作符壓入到棧中。有一點需要注意，隻有在遇到" ) "的情況下我們才彈出" ( "，其他情況我們都不會彈出" ( "。
5)如果我們讀到了輸入的末尾，則将棧中所有元素依次彈出。
下面以a+b*c+(d*e+f)*g為例子來講講計算機的轉換過程。下面在描述棧的情況是直接用文字描述了，由左到右為棧底到棧頂。空表示棧空
由左向右周遊表達式，首先遇到a，直接将其輸出。
此時輸出為：a
棧的情況為：空
繼續周遊，遇到+，将其放入棧中。
此時輸出為：a
棧的情況為：+
繼續周遊，遇到b，直接将其輸出。
此時輸出為：ab
棧的情況為：+
繼續周遊，遇到*，因為*的優先級大于棧頂的+，是以将*放入棧内。
此時輸出為：ab
棧的情況為：+*
繼續周遊，遇到c，直接将其輸出。
此時輸出為：abc
棧的情況為：+*
繼續周遊，遇到+，因為+的優先級低于棧頂的*，故将*彈出；然後新的棧頂元素的+與這個+優先級相同，故也要彈出現在棧頂的+；然後棧空了，将現在這個+放入棧中。
此時輸出為：abc*+
棧的情況為：+
繼續周遊，遇到(，直接将其放入棧中，不遇到)不會将(彈出。
此時輸出為：abc*+
棧的情況為：+(
繼續周遊，遇到d，直接将其輸出。
此時輸出為：abc*+d
棧的情況為：+(
繼續周遊，遇到*，因為棧頂為(,不遇到)不将(彈出,故直接将*放入棧中。
此時輸出為：abc*+d
棧的情況為：+(*
繼續周遊，遇到e，直接将其輸出。
此時輸出為：abc*+de
棧的情況為：+(*
繼續周遊，遇到+，因為+比棧頂*的優先級低，故将*彈出；新的棧頂元素為(,不遇到)不彈出(,故将+放入棧中。
此時輸出為：abc*+de*
棧的情況為：+(+
繼續周遊，遇到f，直接将其輸出。
此時輸出為：abc*+de*f
棧的情況為：+(+
繼續周遊，遇到),直接将棧中元素依次彈出并輸出直到遇到(為止，注意：(彈出但不輸出。
此時輸出為：abc*+de*f+
棧的情況為：+
繼續周遊，遇到*，因為*的優先級大于棧頂元素+的優先級，故直接将*入棧。
此時輸出為：abc*+de*f+
棧的情況為：+*
繼續周遊，遇到g，直接将其輸出。
此時輸出為：abc*+de*f+g
棧的情況為：+*
繼續周遊，為空，周遊結束。将棧内元素依次彈出。
此時輸出為：abc*+de*f+g*+
棧的情況為：空
至此，中綴表達式轉字尾已經全部完成，結果為abc*+de*f+g*+。
代碼實作
源代碼
代碼是用C++寫的，不過還是用的面向過程的思路。代碼如下：
//中綴表達式轉字尾
#include
#include
#include
using namespace std;
int prio(char op) { //給運算符優先級排序
int priority;
if (op == '*' || op == '/')
priority = 2;
if (op == '+' || op == '-')
priority = 1;
if (op == '(')
priority = 0;
return priority;
}
bool Trans(string &str,string &str1) { //引用傳遞
stack s; //定義一個char類型的棧s
int i;
for (i = 0; i
if (str[i] >= '0' && str[i] <= '9') { //如果是數字，直接入棧
str1+=str[i];
}
else { //否則不是數字
if (s.empty()) //棧空則入站
s.push(str[i]);
else if (str[i] == '(') //左括号入棧
s.push(str[i]);
else if (str[i] == ')') { //如果是右括号，隻要棧頂不是左括号，就彈出并輸出
while (s.top() != '(') {
str1+= s.top();
s.pop();
}
s.pop(); //彈出左括号，但不輸出
}
else {
while (prio(str[i]) <= prio(s.top())) { //棧頂優先級大于等于目前運算符，則輸出
str1+= s.top();
s.pop();
if (s.empty()) //棧為空，停止
break;
}
s.push(str[i]); //把目前運算符入棧
}
}
}
while (!s.empty()) { //最後，如果棧不空，則彈出所有元素并輸出
str1+= s.top();
s.pop();
}
return true;
}
int main() { //主程式
string infix;
string postfix;
cout << "請輸入中綴表達式：" << infix << endl;
cin >> infix;
Trans(infix,postfix);
cout << "字尾表達式為：" << postfix << endl;
return 1;
}
程式測試
這裡我們就用a+b*c+(d*e+f)*g的執行個體1+2*3+(4*5+6)*7來測試我們的程式，可見運作結果為123*+45*6+7*+，計算正确。
intopost.png
總結
在寫這段小程式時有一些不小的收獲。畢竟是一個初學者，犯的錯誤都是很低級的知識性錯誤，了解不到位，基礎不紮實。這裡要感謝我的大學同學白洋耐心地教我。
1)string類的對象在沒有初始化大小的情況下不要用其下标運算，會出現string subscript out of range(下标越界)的錯誤。在第三次執行循環時出現，大概是因為string對象的預設大小為2個位元組。
2)string類的對象不以'\0'結尾，要與C語言區分開來，判斷其結束時用size()函數。size() 函數傳回的是其大小，然後下标是以0開始的，是以最大到size-1。
3)函數調用進行形實結合時要用引用傳遞。
4)#include的使用。