这段时间，上海青浦华为练秋湖研发中心第一批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])
来自：数据结构与算法
