?LeetCode刷題實(shí)戰(zhàn)150：逆波蘭表達(dá)式求值
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Note:
Division between two integers should truncate toward zero.
The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.
題意
示例?1：
輸入: ["2", "1", "+", "3", "*"]
輸出: 9
解釋: 該算式轉(zhuǎn)化為常見的中綴算術(shù)表達(dá)式為：((2?+ 1) * 3) = 9
示例?2：
輸入: ["4", "13", "5", "/", "+"]
輸出: 6
解釋: 該算式轉(zhuǎn)化為常見的中綴算術(shù)表達(dá)式為：(4?+ (13?/ 5)) = 6
示例?3：
輸入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
輸出: 22
解釋:
該算式轉(zhuǎn)化為常見的中綴算術(shù)表達(dá)式為：
??((10?* (6?/ ((9?+ 3) * -11))) + 17) + 5
= ((10?* (6?/ (12?* -11))) + 17) + 5
= ((10?* (6?/ -132)) + 17) + 5
= ((10?* 0) + 17) + 5
= (0?+ 17) + 5
= 17?+ 5
= 22
解題
public?class?Solution?{
????public?int?evalRPN(String[] tokens)?{
????????LinkedListstack?= new?LinkedList<>();
????????for(String string?: tokens){
????????????switch?(string){
????????????????case?"+":
????????????????????stack.push(stack.pop() + stack.pop());
????????????????????break;
????????????????case?"-":
????????????????????stack.push(- stack.pop() + stack.pop());
????????????????????break;
????????????????case?"*":
????????????????????stack.push(stack.pop() * stack.pop());
????????????????????break;
????????????????case?"/":
????????????????????Integer num1 = stack.pop();
????????????????????Integer num2 = stack.pop();
????????????????????stack.push(num2 / num1);
????????????????????break;
????????????????default:
????????????????????stack.push(Integer.parseInt(string));
????????????}
????????}
????????return?stack.pop();
????}
}