网上看到得物的一名员工被裁，title是技术专家，年龄是35+。最后为了能留下，哀求HRBP负责人能不能不裁员。
别看有些企业平时讲什么企业精神，团队精神，其实在裁员的时候是最无情的，很少因为哀求被留下的，裁员名单下来之后，恨不得你赶紧走。这个时候不要卑躬屈膝，低三下四，要硬气一点。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第150题：逆波兰表达式求值。
问题描述
来源：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); } else if (token.equals( "-")) { //减法 stack.push(num2 - num1); } else if (token.equals( "*")) { //乘法 stack.push(num2 * num1); } else if (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); else if (token[0] == '-') {//减法 stk.push(num2 - num1); } else if (token[0] == '*') {//乘法 stk.push(num2 * num1); } else if (token[0] == '/') {//除法 stk.push(num2 / num1); } } else {// 如果是数字，就把他压入到栈中 stk.push(stoi(token)); } } // 最后栈中只有一个元素，取出即可 return stk.top(); } // 判断是否是符号 bool isSignal(string &token) { return "+" == token || "-" == token || "*" == token || "/" == token; }
Python：
def evalRPN(self, tokens): stack = [] for token in tokens: if token in '+-*/': # 判断是否是符号 num1 = stack.pop() num2 = stack.pop() stack.append(str(int(eval(num2 + token + num1)))) else: stack.append(token) return int(stack[0])笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴