leetcode筆記：Evaluate Reverse Polish Notation（逆波蘭式的計算）

一. 題目描述

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,
operator； 如果E是 (E1) 形式的表達式，則 E1 的後綴式就是E的後綴式。

一個實際例子如下：

下面以(a+b)*c為例子進行說明：
(a+b)*c的逆波蘭式為ab+c*，假設計算機把ab+c*按從左到右的順序壓入棧中，並且按照遇到運算符就把棧頂兩個元素出棧，執行運算，得到的結果再入棧的原則來進行處理，那麼ab+c*的執行結果如下：

a入棧（0位置）； b入棧（1位置）； 遇到運算符“+”，將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的問題；可能需要進一步考慮操作數是其他數據類型的情況，如浮點數；其他邊界條件是否需要考慮等等。。。