150. 逆ポーランド記法の評価

150. 逆ポーランド表現の評価 #

あなたに文字列配列 tokens が与えられます。これは逆ポーランド記法に基づいて表現された算術式を表します。

この式を計算してください。式の値を表す整数を返します。

注意：

有効な演算子は '+'、'-'、'*' および '/' です。

各オペランド（演算対象）は整数または別の式である可能性があります。

2 つの整数間の除算は常に ゼロに切り捨て されます。

式にはゼロ除算は含まれません。

入力は逆ポーランド記法で表現された算術式です。

答えおよびすべての中間計算結果は 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 + ) * ) です。

逆ポーランド表現には以下の 2 つの主な利点があります：

括弧を取り除くことで式に曖昧さがなくなり、上記の式は 1 2 + 3 4 + * と書いても順序に従って正しい結果を計算できます。

スタック操作に適しており、数字に出会ったらスタックに入れ、演算子に出会ったらスタックのトップから 2 つの数字を取り出して計算し、結果をスタックに押し込みます。

スタック#

考え方として、逆ポーランド表現の文字列コンテナが与えられた場合、スタックの方法を直接使用して問題を解決します。

数字の文字列に出会ったら、直接スタックに入れます。
演算子の文字列に出会ったら、右オペランドをポップし、次に左オペランドをポップして、実行結果をスタックに入れます。

最初に書いたコード：

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 を引くとオーバーフローが発生します。

2 回目の考え方

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. 逆ポーランド表現の評価 #