1. 題目描述

2. 解題思路

逆波蘭表達(dá)式由波蘭的邏輯學(xué)家盧卡西維茲提出，它的特點(diǎn)是：沒(méi)有括號(hào)，運(yùn)算符總是放在和它相關(guān)的操作數(shù)之后。因此，逆波蘭表達(dá)式也稱后綴表達(dá)式，它嚴(yán)格遵循「從左到右」的運(yùn)算。

在我們平時(shí)生活中，使用的算式則是一種中綴表達(dá)式，如 ( 1 + 2 ) * ( 3 + 4 )。

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

計(jì)算逆波蘭表達(dá)式的值時(shí)，使用一個(gè)棧存儲(chǔ)操作數(shù)，從左到右遍歷逆波蘭表達(dá)式，進(jìn)行如下操作：

• 從左至右掃描該算術(shù)表達(dá)式，從第一個(gè)字符開(kāi)始判斷，如果該字符是數(shù)字，則將數(shù)字入棧；
• 如果不是數(shù)字，該字符則是運(yùn)算符，如果遇到運(yùn)算符，則將棧里面的兩個(gè)操作數(shù)出棧，其中先出棧的是右操作數(shù)，后出棧的是左操作數(shù)， 使用運(yùn)算符對(duì)兩個(gè)操作數(shù)進(jìn)行運(yùn)算，將運(yùn)算得到的新操作數(shù)入棧。

整個(gè)逆波蘭表達(dá)式遍歷完畢之后，棧內(nèi)只有一個(gè)元素，該元素即為逆波蘭表達(dá)式的值。

3. 動(dòng)圖演示

來(lái)看個(gè)動(dòng)圖

4. 代碼實(shí)現(xiàn)

有一點(diǎn)需要注意，num 1 和 num2 進(jìn)行運(yùn)算的時(shí)候，num1 是右操作數(shù)，num2 是左操作數(shù)，別寫反了！?。?/p>

代碼示例

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> st;
        for (auto& str : tokens) {
            if (str == "+" || str == "-" || str == "*" || str == "/") {
                auto num1 = st.top();
                st.pop();
                auto num2 = st.top();
                st.pop();

                if (str == "+") {
                    st.push(num2 + num1);
                }
                else if (str == "-") {
                    st.push(num2 - num1);
                }
                else if (str == "*") {
                    st.push(num2 * num1);
                }
                else if (str == "/") {
                    st.push(num2 / num1);
                }
            }
            else {
                st.push(stoi(str)); // 如果是操作數(shù)就入棧，因?yàn)檫@是字符，所以要轉(zhuǎn)成數(shù)字
            }
        }
        return st.top();
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)逆波蘭表達(dá)式的例題詳解的文章就介紹到這了,更多相關(guān)C++逆波蘭表達(dá)式內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論