精品推荐：
《征服数据结构》专栏：50多种数据结构彻底征服
《经典图论算法》专栏：50多种经典图论算法全部掌握
这段时间，上海青浦华为练秋湖研发中心第一批3000名研发人员已经入驻，预计明年春节前后，大约25000人进驻办公，明年年底，完成约30000人。
华为青浦研发中心也为应届生提供了公寓，公寓有华为智慧屏，松下洗衣机，智能马桶，华为门锁，可以入住两年。从公寓关门到公司打卡五分钟不到的路程，这在上海普遍一个小时的上班时间来说已经非常非常近了。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第150题：逆波兰表达式求值。
问题描述
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
1 <= tokens.length <= 10^4
tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数
问题分析
public int evalRPN(String[] tokens) {
Stack<Integer> 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);
}
public:
int evalRPN(vector<string> &tokens) {
stack<int> 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;
}
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])
数组，稀疏表(Sparse Table)，单向链表，双向链表，块状链表，跳表，队列和循环队列，双端队列，单调队列，栈，单调栈，双端栈，散列表，堆，字典树(Trie树)，ArrayMap，SparseArray，二叉树，二叉搜索树(BST)，笛卡尔树，AVL树，树堆(Treap)，FHQ-Treap，哈夫曼树，滚动数组，差分数组，LRU缓存，LFU缓存
……
图的介绍，图的表示方式，邻接矩阵转换，广度优先搜索(BFS)，深度优先搜索(DFS)，A*搜索算法，迭代深化深度优先搜索(IDDFS)，IDA*算法，双向广度优先搜索，迪杰斯特拉算法(Dijkstra)，贝尔曼-福特算法(Bellman-Ford)，SPFA算法，弗洛伊德算法(Floyd)，卡恩(Kahn)算法，基于DFS的拓扑排序，约翰逊算法(Johnson)
……
