【LeetCode】150. 逆波兰表达式求值(ASCII码)

今日学习的文章链接和视频链接

leetcode题目地址：150. 逆波兰表达式求值

代码随想录题解地址：代码随想录

题目简介

即将后缀表达式转换成中缀表达式并计算。

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

看到题目的第一想法(可以贴代码）

1. 逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

public int evalRPN(String[] tokens) {Stack<String> st = new Stack<>();for (String i : tokens){if (i.charAt(0)>=48 && i.charAt(0)<=57 || i.charAt(0)=='-' && i.length() != 1){st.push(i);}else if (i.charAt(0)=='+'){int num1 = Integer.parseInt(st.pop());int num2 = Integer.parseInt(st.pop());int sum = num1 + num2;st.push(Integer.toString(sum));}else if (i.charAt(0)=='-' && i.length() == 1){int num1 = Integer.parseInt(st.pop());int num2 = Integer.parseInt(st.pop());int sum = num2 - num1;st.push(Integer.toString(sum));}else if (i.charAt(0)=='*'){int num1 = Integer.parseInt(st.pop());int num2 = Integer.parseInt(st.pop());int sum = num1 * num2;st.push(Integer.toString(sum));}else if (i.charAt(0)=='/'){int num1 = Integer.parseInt(st.pop());int num2 = Integer.parseInt(st.pop());  int sum = num2 / num1;st.push(Integer.toString(sum));}}return Integer.parseInt(st.pop());
}

实现过程中遇到哪些困难

无

看完代码随想录之后的想法

【解题思路】利用栈解，与我的一致，但用的是Deque。

【想法】

1. 好像一般都用Deque-LinkedList数据类型而不用Stack。

2. 先判定加减乘除更快。

看完视频自己写的ACC：

public int evalRPN(String[] tokens) {Deque<Integer> st = new LinkedList<>();for (String i : tokens){if (i.equals("+")){st.push(st.pop()+st.pop());}else if (i.equals("-")){st.push(-st.pop()+st.pop());}else if (i.equals("*")){st.push(st.pop()*st.pop());}else if (i.equals("/")){int temp1 = st.pop();int temp2 = st.pop();st.push(temp2/temp1);}else {st.push(Integer.valueOf(i));}}return st.pop();
}