Leetcode——150. 逆波兰表达式求值

题解一

思路

和上一期1047. 删除字符串中的所有相邻重复项没差太多，基本思想都一样，就是读取输入的数据，如果是运算符，就进行相应的运算，然后把运算结果压栈。

代码

class Solution {public int evalRPN(String[] tokens) {Deque<Integer> stack = new ArrayDeque<>();for(String str : tokens){if("+".equals(str)){stack.push(stack.pop() + stack.pop());}else if("-".equals(str)){stack.push(-stack.pop() + stack.pop());}else if("*".equals(str)){stack.push(stack.pop() * stack.pop());}else if("/".equals(str)){int temp1 = stack.pop();int temp2 = stack.pop();stack.push(temp2 / temp1);}else{stack.push(Integer.parseInt(str));}}return stack.pop();}
}

总结

这里面的判断条件，看Carl的代码随想录里说，Leetcode里面的内置jdk有问题，如果写“+” == str会报错，我测试了一下，确实是这样的，在IDEA里“+” == str是可以正常运行的。

这道题第一次没想到这个做法，因为与上一道题隔了一段时间去做，第一反应是把所有数组元素全部压进栈中，然后进行运算，反正思路很奇怪，因为在运算过程中可能会出现连消的效果（像那个祖玛一样），和中邪了一样疯狂想用递归求出结果哈哈哈，下面是碰壁了的代码。

import java.util.ArrayDeque;
import java.util.Deque;public class Solution {public int evalRPN(String[] tokens) {Deque<String> stack = new ArrayDeque<>();for (String str : tokens) {stack.push(str);calculate(stack);}return Integer.parseInt(stack.pop());}public void calculate(Deque stack) {int a = 0;int b = 0;String temp = "";try {temp = (String) stack.pop();a = Integer.parseInt(temp);} catch (NumberFormatException e) {stack.push(temp);return;}try {if (!stack.isEmpty()) {temp = (String) stack.pop();b = Integer.parseInt(temp);}} catch (NumberFormatException e) {stack.push(temp);return;}if (!stack.isEmpty()) {temp = (String) stack.pop();}if (temp.equals("+")) {int result = a + b;stack.push(String.valueOf(result));} else if (temp.equals("-")) {int result = a - b;stack.push(String.valueOf(result));} else if (temp.equals("*")) {int result = a * b;stack.push(String.valueOf(result));} else {int result = a / b;stack.push(String.valueOf(result));}calculate(stack);}
}