程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode筆記:Evaluate Reverse Polish Notation(逆波蘭式的計算)

leetcode筆記:Evaluate Reverse Polish Notation(逆波蘭式的計算)

編輯:C++入門知識

leetcode筆記:Evaluate Reverse Polish Notation(逆波蘭式的計算)


一. 題目描述

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:

[2, 1, +, 3, *] -> ((2 + 1) * 3) -> 9

[4, 13, 5, /, +] -> (4 + (13 / 5)) -> 6

二. 題目分析

該題考查逆波蘭式,也叫後綴表達式(將運算符寫在操作數之後)。假設有一個表達式E,其後綴形式定義如下:

如果E是一個變量或常量,則E的後綴式是E本身; 如果E是E1 operator E2形式的表達式,這裡 operator 是如何二元操作符,則E的後綴式為E1, E2,
operator; 如果E是 (E1) 形式的表達式,則 E1 的後綴式就是E的後綴式。

一個實際例子如下:

下面以(a+b)*c為例子進行說明:
(a+b)*c的逆波蘭式為ab+c*,假設計算機把ab+c*按從左到右的順序壓入棧中,並且按照遇到運算符就把棧頂兩個元素出棧,執行運算,得到的結果再入棧的原則來進行處理,那麼ab+c*的執行結果如下:

a入棧(0位置); b入棧(1位置); 遇到運算符“+”,將ab出棧,執行a+b的操作,得到結果d=a+b,再將d入棧(0位置); c入棧(1位置); 遇到運算符“*”,將dc出棧,執行d*c的操作,得到結果e,再將e入棧(0位置)。

經過以上運算,計算機就可以得到(a+b)*c的運算結果e了。

逆波蘭式計算等式的實現非常容易,使用堆棧即可完成。在程序中,需要實現整數與字符串之間的相互轉換。

三. 示例代碼

#include 
#include 
#include 

using namespace std;

class Solution
{
public:
    int str2int(string s) // string轉int
    {
        int result = 0;
        int base = 1;
        int t = 1; // 正負號

        if (s[0] == '-')
            t = -1;

        for (int i = s.size() - 1; i >= 0; --i)
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                result += base * (s[i] - '0');  
                base *= 10;
            }
        }

        return result * t;
    }

    int evalRPN(vector &tokens)
    {
        stack k;

        for (int i = 0; i < tokens.size(); ++i)
        {
            if (tokens[i] == + || tokens[i] == - || tokens[i] == * || tokens[i] == /)
            {
                int Num2 = k.top(); // 第一個取出的是右操作數
                k.pop();
                int Num1 = k.top(); // 左操作數
                k.pop();

                if (tokens[i] == +){
                    k.push(Num1 + Num2);
                }
                else if (tokens[i] == -){
                    k.push(Num1 - Num2);
                }
                else if (tokens[i] == *){
                    k.push(Num1 * Num2);
                }
                else if (tokens[i] == /){
                    k.push(Num1 / Num2);
                }
            }
            else
                k.push(str2int(tokens[i]));
        }
        return k.top(); // 最後棧剩下一個元素,就是結果
    }
};

這裡寫圖片描述

這裡寫圖片描述

四. 小結

雖然整個思路簡單,但在編寫程序時還是有一些細節的問題,如從棧彈出兩個操作數,第一個彈出的是右操作數,第二個是左操作數;是否需要考慮string轉int的問題;可能需要進一步考慮操作數是其他數據類型的情況,如浮點數;其他邊界條件是否需要考慮等等。。。

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved