**一. 題目描述** Evaluate the value of an arithmetic expression in Reverse Polish Notation.? Valid operators are +, -, *, /. Each operand may be an integer or another expression.? Some examples: `["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9` `["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6` **二. 題目分析** 該題考查逆波蘭式，也叫后綴表達式（將運算符寫在操作數之后）。假設有一個表達式E，其后綴形式定義如下： 1. 如果E是一個變量或常量，則E的后綴式是E本身； 2. 如果E是E1 operator E2形式的表達式，這里 operator 是如何二元操作符，則E的后綴式為E1, E2,? operator； 3. 如果E是 (E1) 形式的表達式，則 E1 的后綴式就是E的后綴式。 一個實際例子如下： 下面以`(a+b)*c`為例子進行說明：? `(a+b)*c`的逆波蘭式為`ab+c*`，假設計算機把`ab+c*`按從左到右的順序壓入棧中，并且按照遇到運算符就把棧頂兩個元素出棧，執行運算，得到的結果再入棧的原則來進行處理，那么`ab+c*`的執行結果如下： 1. a入棧（0位置）； 2. b入棧（1位置）； 3. 遇到運算符`“+”`，將`a`和`b`出棧，執行`a+b`的操作，得到結果`d=a+b`，再將`d`入棧（0位置）； 4. c入棧（1位置）； 5. 遇到運算符`“*”`，將`d`和`c`出棧，執行`d*c`的操作，得到結果`e`，再將`e`入棧（0位置）。 經過以上運算，計算機就可以得到`(a+b)*c`的運算結果`e`了。 逆波蘭式計算等式的實現非常容易，使用堆棧即可完成。在程序中，需要實現整數與字符串之間的相互轉換。 **三. 示例代碼** ~~~ #include <iostream> #include <vector> #include <stack> using namespace std; class Solution { public: int str2int(string s) // string轉int { int result = 0; int base = 1; int t = 1; // 正負號 if (s[0] == '-') t = -1; for (int i = s.size() - 1; i >= 0; --i) { if (s[i] >= '0' && s[i] <= '9') { result += base * (s[i] - '0'); base *= 10; } } return result * t; } int evalRPN(vector<string> &tokens) { stack<int> k; for (int i = 0; i < tokens.size(); ++i) { if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") { int Num2 = k.top(); // 第一個取出的是右操作數 k.pop(); int Num1 = k.top(); // 左操作數 k.pop(); if (tokens[i] == "+"){ k.push(Num1 + Num2); } else if (tokens[i] == "-"){ k.push(Num1 - Num2); } else if (tokens[i] == "*"){ k.push(Num1 * Num2); } else if (tokens[i] == "/"){ k.push(Num1 / Num2); } } else k.push(str2int(tokens[i])); } return k.top(); // 最后棧剩下一個元素，就是結果 } }; ~~~   **四. 小結** 雖然整個思路簡單，但在編寫程序時還是有一些細節的問題，如從棧彈出兩個操作數，第一個彈出的是右操作數，第二個是左操作數；是否需要考慮string轉int的問題；可能需要進一步考慮操作數是其他數據類型的情況，如浮點數；其他邊界條件是否需要考慮等等。。。 參考鏈接：[http://baike.baidu.com/link?url=q-x6bMceggqTTRtvBPKuH69fVoEyi6C_ylbEe9lvIHhlruHZ8bdQ6vGuSibCxvw5DWEMWeR98EmWs0Ineo1OTq](http://baike.baidu.com/link?url=q-x6bMceggqTTRtvBPKuH69fVoEyi6C_ylbEe9lvIHhlruHZ8bdQ6vGuSibCxvw5DWEMWeR98EmWs0Ineo1OTq)