關於字符串表達式求值，應該是程序猿們機試或者面試時候常見問題之一，昨天參加國內某IT的機試，壓軸便為此題，今天抽空對其進行了研究。
算術表達式中最常見的表示法形式有 中綴、前綴和 後綴表示法。中綴表示法是書寫表達式的常見方式，而前綴和後綴表示法主要用於計算機科學領域。
中綴表示法
中綴表示法是算術表達式的常規表示法。稱它為 中綴表示法是因為每個操作符都位於其操作數的中間，這種表示法只適用於操作符恰好對應兩個操作數的時候（在操作符是二元操作符如加、減、乘、除以及取模的情況下）。對以中綴表示法書寫的表達式進行語法分析時，需要用括號和優先規則排除多義性。
Syntax: operand1 operand2 Example: (A+B)*C-D/(E+F)
前綴表示法
前綴表示法中，操作符寫在操作數的前面。這種表示法經常用於計算機科學，特別是編譯器設計方面。為紀念其發明家 ― Jan Lukasiewicz（請參閱參考資料），這種表示法也稱 波蘭表示法。
Syntax : operand1 operand2 Example : -*+ABC/D+EF
後綴表示法
在後綴表示法中，操作符位於操作數後面。後綴表示法也稱 逆波蘭表示法（reverse Polish notation，RPN），因其使表達式求值變得輕松，所以被普遍使用。
Syntax : operand1 operand2 Example : AB+C*DEF+/-
字符串表達式求值，一般來說采用如下方式:
一. 中綴表達式到後綴表達式的轉換
要把表達式從中綴表達式的形式轉換成用後綴表示法表示的等價表達式，必須了解操作符的優先級和結合性。 優先級或者說操作符的強度決定求值順序；優先級高的操作符比優先級低的操作符先求值。 如果所有操作符優先級一樣，那麼求值順序就取決於它們的 結合性。操作符的結合性定義了相同優先級操作符組合的順序（從右至左或從左至右）。
Left associativity : A+B+C = (A+B)+^B^C = A^(B^C)
轉換過程包括用下面的算法讀入中綴表達式的操作數、操作符和括號：
二. 後綴表達式求值
對後綴表達式求值比直接對中綴表達式求值簡單。在後綴表達式中，不需要括號，而且操作符的優先級也不再起作用了。您可以用如下算法對後綴表達式求值：
好了，基本思路討論完畢，我們開始動手寫代碼，此段代碼假設表達式中的預算符只包括四大基本運算符+、-、*、/，為了簡化代碼，我們也假設表達式中的數字只包括1-9。
函數getPostfixExp用來將一個中綴表達式轉換為後綴表達式(也就是逆波蘭式).
getPostfixExp(&<> (!operator_stack.empty() && isOperator(operator_stack.top()) && priority(operator_stack.top()) >= (p == (p == (operator_stack.top() != (!
其中isOperator函數如下：
isOperator(
其中的priority函數如下：
priority( (a == || a == = (a == || a == =
得到了後綴表達式，開始我們的求值之旅吧！
postfixCalculate(&<>
* / + -
- result =
其中getTwoNums函數如下：
getTwoNums(stack<>& num_stack, & first, &==
好了，全部的代碼結束了，寫個main函數試試吧！
>> postfix =<< postfix <<<< postfixCalculate(postfix) <<
寫在最後的話：
字符串表達式求值方法很多，本文中利用stack結合優先級的方式，解決了這個問題。其他的方法，有表達式樹的方式，編譯原理的書上有講解，大家可以結合原理，自己動手實現生成表達式樹的代碼，然後求值就變得so easy了，當然也有與上面兩者迥然不同的方式，大家舉一反三，多研究！
