一. 題目描述
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,其後綴形式定義如下:
如果E是一個變量或常量,則E的後綴式是E本身; 如果E是E1 operator E2形式的表達式,這裡 operator 是如何二元操作符,則E的後綴式為E1, E2,一個實際例子如下:
下面以(a+b)*c
為例子進行說明:
(a+b)*c
的逆波蘭式為ab+c*
,假設計算機把ab+c*
按從左到右的順序壓入棧中,並且按照遇到運算符就把棧頂兩個元素出棧,執行運算,得到的結果再入棧的原則來進行處理,那麼ab+c*
的執行結果如下:
“+”
,將a
和b
出棧,執行a+b
的操作,得到結果d=a+b
,再將d
入棧(0位置); c入棧(1位置); 遇到運算符“*”
,將d
和c
出棧,執行d*c
的操作,得到結果e
,再將e
入棧(0位置)。
經過以上運算,計算機就可以得到(a+b)*c
的運算結果e
了。
逆波蘭式計算等式的實現非常容易,使用堆棧即可完成。在程序中,需要實現整數與字符串之間的相互轉換。
三. 示例代碼
#include
#include
#include
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 &tokens)
{
stack 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的問題;可能需要進一步考慮操作數是其他數據類型的情況,如浮點數;其他邊界條件是否需要考慮等等。。。