C++實現(xiàn)逆波蘭表達式的例題詳解

更新時間：2022年12月21日 08:18:58 作者：Albert Edison

逆波蘭表達式由波蘭的邏輯學家盧卡西維茲提出，它的特點是：沒有括號，運算符總是放在和它相關的操作數(shù)之后。本文將通過例題講講如何利用C++實現(xiàn)逆波蘭表達式，需要的可以參考一下

1. 題目描述

2. 解題思路

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

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

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

計算逆波蘭表達式的值時，使用一個棧存儲操作數(shù)，從左到右遍歷逆波蘭表達式，進行如下操作：

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

整個逆波蘭表達式遍歷完畢之后，棧內只有一個元素，該元素即為逆波蘭表達式的值。

3. 動圖演示

來看個動圖

4. 代碼實現(xiàn)

有一點需要注意，num 1 和 num2 進行運算的時候，num1 是右操作數(shù)，num2 是左操作數(shù)，別寫反了?。?！

代碼示例

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ù)就入棧，因為這是字符，所以要轉成數(shù)字
            }
        }
        return st.top();
    }
};

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

您可能感興趣的文章: