日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學(xué)無先后，達(dá)者為師

網(wǎng)站首頁 編程語言 正文

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

作者：Albert?Edison ? 更新時間： 2023-01-21 編程語言

1. 題目描述

2. 解題思路

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

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

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

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

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

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

3. 動圖演示

來看個動圖

4. 代碼實現(xiàn)

有一點需要注意，num 1 和 num2 進(jìn)行運算的時候，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ù)就入棧，因為這是字符，所以要轉(zhuǎn)成數(shù)字
            }
        }
        return st.top();
    }
};

原文鏈接：https://blog.csdn.net/m0_63325890/article/details/128391664

欄目分類
最近更新