华为青浦公寓，爽的一批，上班5分钟通勤，中午回来休息 。。。

专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

这段时间，上海青浦华为练秋湖研发中心第一批3000名研发人员已经入驻，预计明年春节前后，大约25000人进驻办公，明年年底，完成约30000人。

华为青浦研发中心也为应届生提供了公寓，公寓有华为智慧屏，松下洗衣机，智能马桶，华为门锁，可以入住两年。从公寓关门到公司打卡五分钟不到的路程，这在上海普遍一个小时的上班时间来说已经非常非常近了。

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

来看下今天的算法题，这题是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算法文档 。