專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

3月19日，騰訊公布了2024年第四季度以及2024年全年的業績。財報顯示，騰訊2024年實現營收6602.6億元，比去年增長8%。凈利潤收入為1940.7億元，比去年增長68%，這樣算下來，凈利潤日均收入約5.3億元。

截至2024年12月31日止年度的總酬金成本為人民幣1128億元（2023年：人民幣1077億元）。而騰訊集團截止到2024年底有110558名員工（2023年：105417名），這樣算下來，員工的人均年收入超過百萬。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第題：逆波蘭表達式求值。

問題描述

來源：LeetCode第150題

難度：中等

給你一個字符串數組 tokens ，表示一個根據逆波蘭表示法表示的算術表達式。請你計算該表達式。返回一個表示表達式值的整數。

示例1：

輸入：tokens = ["2","1","+","3","*"] 輸出：9 解釋：該算式轉化為常見的中綴算術表達式為：((2 + 1) * 3) = 9

示例2：

輸入：tokens = ["4","13","5","/","+"] 輸出：6 解釋：該算式轉化為常見的中綴算術表達式為：(4 + (13 / 5)) = 6

• 1 <= tokens.length <= 10^4

• tokens[i] 是一個算符（"+"、"-"、"*" 或 "/"），或是在范圍 [-200, 200] 內的一個整數

問題分析

這題說的是給定一個逆波蘭表示法的算術表達式，讓我們求它的值。我們平時書寫的表達式都是中綴表達式，運算符在中間，操作數在兩邊，比如a+b。逆波蘭表達式就是 后綴表達式 ，操作數在前，運算符在后，比如 a b + 。還有一個是前綴表達式，是波蘭表達式，運算符在前，操作數在后，比如 + a b 。

對于我們人來說中綴表達式是最容易計算的，但對于計算機來說更容易計算的是前綴表達式和后綴表達式。關于前，中，后三種表達式的相互轉換有堆棧法，二叉樹法和括號法，具體可以看下 《 中的第十三章。我們這里主要來看下逆波蘭表達式是怎么求值的。

對于逆波蘭表達式的計算我們只需要使用一個棧即可，遍歷字符串數組，如果遇到數字就入棧，如果是運算符就從棧中彈出兩個數字，對它們進行運算， 注意先出棧的是右值，后出棧的是左值 ，運算的結果需要入棧，一直重復上面的步驟，直到字符串數組遍歷完為止，然后棧中只剩下一個值，這個值就是我們要求的結果。

JAVA：

 public int evalRPN(String[] tokens) {     Stack stack =  new Stack<>();     int num1, num2;     for (String token : tokens) {         if (isSignal(token)) {             // 如果是運算符，就從棧中連續彈出兩個數字。             num1 = stack.pop();// 右值             num2 = stack.pop();// 左值             if (token.equals("+")) {//加法                 stack.push(num2 + num1);             } elseif (token.equals("-")) {//減法                 stack.push(num2 - num1);             } elseif (token.equals("*")) {//乘法                 stack.push(num2 * num1);             } elseif (token.equals("/")) {//除法                 stack.push(num2 / num1);             }         } else { // 如果是數字，就把他壓入到棧中             stack.push(Integer.parseInt(token));         }     }     // 最后棧中只有一個元素，取出即可     return stack.pop(); } // 判斷是否是符號 private boolean isSignal(String token) {     return"+".equals(token) || "-".equals(token)             || "*".equals(token) || "/".equals(token); }

C++：

public:     int evalRPN(vector

 &tokens) {         stack

 stk;         int num1, num2;         for (string &token: tokens) {             if (isSignal(token)) {                 // 如果是運算符，就從棧中連續彈出兩個數字。                 num1 = stk.top();// 右值                 stk.pop();                 num2 = stk.top();// 左值                 stk.pop();                 if (token[0] == '+')//加法                     stk.push(num2 + num1);                 elseif (token[0] == '-') {//減法                     stk.push(num2 - num1);                 } elseif (token[0] == '*') {//乘法                     stk.push(num2 * num1);                 } elseif (token[0] == '/') {//除法                     stk.push(num2 / num1);                 }             } else {// 如果是數字，就把他壓入到棧中                 stk.push(stoi(token));             }         }         // 最后棧中只有一個元素，取出即可         return stk.top();     }     // 判斷是否是符號     bool isSignal(string &token) {         return"+" == token || "-" == token                || "*" == token || "/" == token;     }

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。