专栏：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算法文档 。