题目
-
概述：给你一个逆波兰表达式，求表达式的值
逆波兰表达式：
也叫后缀表达式
一个表达式E的后缀形式可以如下定义：
（1）如果E是一个变量或常量，则E的后缀式是E本身
（2）如果E是E1 op E2形式的表达式，这里op是二元操作符，则E的后缀表达式是E1'E2'op，这里E1'和E2'分别为E1和E2的后缀式
（3）如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式有效的运算符包括+，-，*，/
整数除法只保留整数部分
给定逆波兰表达式总是有效的
输入：逆波兰表达式字符串列表
输入子项：字符串（整数或者运算符）
输出：逆波兰表达式的值
出处：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
思路
由于需要存储字符串进行后面的运算，所以采用栈实现
-
遍历逆波兰表达式字符串列表，对于每一个字符串S
- S是运算符 => 弹出栈顶元素两次，用第二次弹出的元素和第一次弹出的元素根据对应的运算符做运算，然后将运算结果放入栈中
- S是整数 => 直接放入栈中
最后栈中唯一元素即为逆波兰表达式的值
代码
class Solution {
public int evalRPN(String[] tokens) {
LinkedList<Integer> stack = new LinkedList<>();
int number;
for (String s : tokens) {
switch (s) {
case "+":
number = stack.pop();
stack.push(stack.pop() + number);
break;
case "-":
number = stack.pop();
stack.push(stack.pop() - number);
break;
case "*":
number = stack.pop();
stack.push(stack.pop() * number);
break;
case "/":
number = stack.pop();
stack.push(stack.pop() / number);
break;
default:
stack.push(Integer.parseInt(s));
break;
}
}
return stack.pop();
}
}
