力扣刷题日记之150.逆波兰表达式求值

今天继续给大家分享一道力扣的做题心得今天这道题目是 150.逆波兰表达式求值

题目如下，题目链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation

1，题目分析

这道题说是一道中等难度的题目，其实如果理解了其中的含义，实际上比简单题还要稍微简单一些，废话不多说我们直接开始分析题目，

这道题最核心的含义就是通过将这个String类型的数组中的数和运算符号按照其运算规则算完然后返回最后算出来的那个值就可以了，仔细看这个运算规则是不是很像是在栈里面运行一样？所有这道题最直接而且高效的办法就是利用栈来做，理解题目意思之后我们做题简直就是游刃有余

2，解题思路

下面是我的最初提交通过的代码大家可以参考一下

class Solution {public int evalRPN(String[] tokens) {int length = tokens.length;Stack<Integer> stack = new Stack<>();for(String token : tokens){int value1,value2;switch(token){case "+" :value1 = stack.pop();value2 = stack.pop();stack.push(value1 + value2);break;case "-" :value1 = stack.pop();value2 = stack.pop();stack.push(value2 - value1);break;case "*" :value1 = stack.pop();value2 = stack.pop();stack.push(value1 * value2);break;case "/" :value1 = stack.pop();value2 = stack.pop();stack.push(value2 / value1);break;default: stack.push(Integer.parseInt(token));break;}}return stack.peek();}
}

具体解题思路就是通过一个for循环将题目所给的这个数组遍历，然后在循环中利用数组中只有运算数字和这个加减乘除这个5类元素的特点我们直接在里面写一个switch结构来进行判断，假如是运算符则弹出栈前面两项来进行对应的运算然后在将结果放入栈顶，假如不是运算符则将数字放入栈内，最后经过循环完毕之后，栈里面就只剩一个最后的结果的数字了这个时候直接返回栈顶元素就是题目的答案了

注意：这个题目所给的数字和运算符都是数目相对的都是可以最后通过这个逆波兰表达式算出来的，也就是不会有数组第一或者第二个元素就是运算符的情况，所有这些特殊情况我们都不需要考虑因为这些情况是不满足这个题目的运算规则的

3，优化后的题解

为了达到打败更多人所有优化了代码但是核心逻辑是不变的，只是优化了一下内容提升了运行效率

import java.util.ArrayDeque;
import java.util.Deque;class Solution {public int evalRPN(String[] tokens) {// 使用 ArrayDeque 替代 StackDeque<Integer> stack = new ArrayDeque<>(tokens.length);for (String token : tokens) {char firstChar = token.charAt(0);// 判断是否为运算符if (token.length() == 1 && (firstChar == '+' || firstChar == '-' || firstChar == '*' || firstChar == '/')) {int b = stack.pop(); // 注意 b 是后弹出的int a = stack.pop(); // a 是先弹出的if (firstChar == '+') stack.push(a + b);else if (firstChar == '-') stack.push(a - b);else if (firstChar == '*') stack.push(a * b);else stack.push(a / b);} else {// 将操作数压入栈stack.push(Integer.parseInt(token));}}// 返回最终计算结果return stack.pop();}public static void main(String[] args) {// 测试代码Solution solution = new Solution();// 示例测试数据String[] tokens1 = {"2", "1", "+", "3", "*"}; // (2 + 1) * 3 = 9String[] tokens2 = {"4", "13", "5", "/", "+"}; // 4 + (13 / 5) = 6String[] tokens3 = {"10", "6", "9", "3", "/", "-", "*", "17", "+", "5", "+"}; // 22System.out.println("Result 1: " + solution.evalRPN(tokens1)); // 输出 9System.out.println("Result 2: " + solution.evalRPN(tokens2)); // 输出 6System.out.println("Result 3: " + solution.evalRPN(tokens3)); // 输出 22}
}