150. 逆波蘭表達式求值

150. 逆波兰表达式求值 #

給你一個字符串數組 tokens ，表示一個根據逆波蘭表示法表示的算術表達式。

請你計算該表達式。返回一個表示表達式值的整數。

注意：

有效的算符為 '+'、'-'、'*' 和 '/' 。

每個操作數（運算對象）都可以是一個整數或者另一個表達式。

兩個整數之間的除法總是 向零截斷 。

表達式中不含除零運算。

輸入是一個根據逆波蘭表示法表示的算術表達式。

答案及所有中間計算結果可以用 32 位 整數表示。

示例 1：
輸入：tokens = ["2","1","+","3","*"]
輸出：9
解釋：該算式轉化為常見的中綴算術表達式為：((2 + 1) * 3) = 9
示例 2：
輸入：tokens = ["4","13","5","/","+"]
輸出：6
解釋：該算式轉化為常見的中綴算術表達式為：(4 + (13 / 5)) = 6
示例 3：
輸入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
輸出：22
解釋：該算式轉化為常見的中綴算術表達式為：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
提示：

1 <= tokens.length <= 10^4

tokens[i] 是一個算符（"+"、"-"、"*" 或 "/"），或是在範圍 [-200, 200] 內的一個整數

逆波蘭表達式：

逆波蘭表達式是一種後綴表達式，所謂後綴就是指算符寫在後面。

平常使用的算式則是一種中綴表達式，如 ( 1 + 2 ) * ( 3 + 4 ) 。

該算式的逆波蘭表達式寫法為 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波蘭表達式主要有以下兩個優點：

去掉括號後表達式無歧義，上式即便寫成 1 2 + 3 4 + * 也可以依據次序計算出正確結果。

適合用棧操作運算：遇到數字則入棧；遇到算符則取出棧頂兩個數字進行計算，並將結果壓入棧中

棧#

思路，給定逆波蘭表達式字符串容器，直接使用棧的方法解決問題。

遇到數字字符串直接入棧。
遇到操作符字符串，先彈出右操作數，再彈出左操作數，將執行結果入棧。

第一次寫的代碼：

class Solution {
public:
    bool isOperator(const string& s) {
        return s == "+" || s == "-" || s == "*" || s == "/";
    }
    int strToint(const string& s) {
        int sum = 0;
        int len = s[0] == '-' ? s.size() - 1 : s.size();
        /* bug 在 size() 接口，size() 返回類型 size_t 為 unsigned int 類型 */
        // for (int i = s.size() - 1, j = 1; i > s.size() - len - 1; --i, j *= 10) {
        //     sum += (s[i] - '0') * j;
        // }
        for (int i = (int)s.size() - 1, j = 1; i > (int)s.size() - len - 1; --i, j *= 10) {
            // signed integer overflow: 147483648 + 2000000000 cannot be represented in type 'int'
            sum += (s[i] - '0') * j;
        }
        return len == s.size() ? sum : -sum;
    }
    string intTostr(int num) {
        string res;
        while (num) {
            res.push_back(num % 10 + 48);
            num /= 10;
        }
        reverse(res.begin(), res.end());
        return res;
        // return to_string(num);
    }
    string operationTwoNum(const string& oper, const string& str1, const string& str2) {
        if (oper == "+") {
            return intTostr(strToint(str1) + strToint(str2));
        }
        else if (oper == "-") {
            return intTostr(strToint(str1) - strToint(str2));
        }
        else if (oper == "*") {
            return intTostr(strToint(str1) * strToint(str2));
        }
        else {
            return intTostr(strToint(str1) / strToint(str2));
        }
    }
    int evalRPN(vector<string>& tokens) {
        stack<string> strStack;
        for (auto& s : tokens) {
            if (isOperator(s)) {
                // 彈出右操作數
                string rightStr = strStack.top();
                strStack.pop();
                // 彈出左操作數
                string leftStr = strStack.top();
                strStack.pop();
                // 結果入棧
                strStack.push(operationTwoNum(s, leftStr, rightStr));
            }
            else {
                strStack.push(s);
            }
        }
        return strToint(strStack.top());
    }
};

上面代碼寫的有很多問題，其中最主要的問題就是溢出問題。

接口函數 size () 返回容器長度，其返回類型是 size_t（unsigned int）當 size () == 0 的時候對其進行減 1 操作就會溢出。

第二次思路

創建 long long 類型的棧。
遇到的字符串不是操作符，就將其轉化為long long類型入棧，這樣棧中就全是數而不是字符串，最後在彈出時就不需進行處理。
遇到的字符串是操作符，就先彈出右操作數，再彈出左操作數，對其進行操作後重新入棧。
最後棧頂就是運算結果。

class Solution {
public:
    long long strTolonglong(const string& s) {
        long long sum = 0; // 轉化結果
        // int count = s[0] == "-" ? (int)s.size() - 1 : (int)s.size(); 
        int leftMostSub = s[0] == '-' ? 0 : - 1; // 避免溢出問題
        for (int i = (int)s.size() - 1, j = 1; i > leftMostSub; --i, j *= 10) {
            sum += (s[i] - '0') * j;
        }
        return leftMostSub ? sum : -sum;
        // return stoll(s); // 也可以直接調用庫函數
    }
    int evalRPN(vector<string>& tokens) {
        stack<long long> llStack;
        for (auto& s : tokens) {
            if (s == "+" || s == "-" || s == "*" || s == "/") {
                // 先彈出右操作數
                long long right = llStack.top();
                llStack.pop();
                // 再彈出左操作數
                long long left = llStack.top();
                llStack.pop();
                
                if (s == "+") {
                    llStack.push(left + right);
                }
                if (s == "-") {
                    llStack.push(left - right);
                }
                if (s == "*") {
                    llStack.push(left * right);
                }
                if (s == "/") {
                    llStack.push(left / right);
                }
            }
            else {
                llStack.push(strTolonglong(s));
            }
        }
        return llStack.top();
    }
};

150. 逆波蘭表達式求值

150. 逆波兰表达式求值#

棧#

150. 逆波兰表达式求值 #