做投资要关注哪些网站,professional wordpress,抄袭网站违法,优设网文案下载目录 题目描述和要求示例解释解题思路算法实现复杂度分析测试和验证总结和拓展参考资料 题目描述和要求
给你一个字符串数组 tokens#xff0c;表示一个根据逆波兰表示法表示的算术表达式。请你计算该表达式#xff0c;并返回一个表示表达式值的整数。
注意#xff1a;
有… 目录 题目描述和要求示例解释解题思路算法实现复杂度分析测试和验证总结和拓展参考资料 题目描述和要求
给你一个字符串数组 tokens表示一个根据逆波兰表示法表示的算术表达式。请你计算该表达式并返回一个表示表达式值的整数。
注意
有效的算符为 ‘’、‘-’、‘*’ 和 ‘/’。每个操作数运算对象都可以是一个整数或者另一个表达式。两个整数之间的除法总是向零截断。表达式中不含除零运算。输入是一个根据逆波兰表示法表示的算术表达式。答案及所有中间计算结果可以用 32 位整数表示。
示例解释
示例 1
输入tokens [“2”,“1”,“”,“3”,“*”] 输出9 解释该算式转化为常见的中缀算术表达式为((2 1) * 3) 9
示例 2
输入tokens [“4”,“13”,“5”,“/”,“”] 输出6 解释该算式转化为常见的中缀算术表达式为(4 (13 / 5)) 6
示例 3
输入tokens [“10”,“6”,“9”,“3”,“”,“-11”,““,”/“,””,“17”,“”,“5”,“”] 输出22 解释该算式转化为常见的中缀算术表达式为
((10 * (6 / ((9 3) * -11))) 17) 5((10 * (6 / (12 * -11))) 17) 5((10 * (6 / -132)) 17) 5((10 * 0) 17) 5(0 17) 517 522解题思路
我们可以使用栈来解决这个问题。遍历 tokens当遇到操作数时将其压入栈中当遇到操作符时从栈中弹出两个操作数进行计算并将结果压入栈中。最终栈中剩下的唯一元素就是表达式的值。
算法实现
import java.util.Stack;public class EvalRPN {public int evalRPN(String[] tokens) {StackInteger stack new Stack();for (String token : tokens) {if (token.equals()) {int b stack.pop();int a stack.pop();stack.push(a b);} else if (token.equals(-)) {int b stack.pop();int a stack.pop();stack.push(a - b);} else if (token.equals(*)) {int b stack.pop();int a stack.pop();stack.push(a * b);} else if (token.equals(/)) {int b stack.pop();int a stack.pop();stack.push(a / b);} else {stack.push(Integer.parseInt(token));}}return stack.pop();}
}复杂度分析
时间复杂度O(n)其中 n 为 tokens 的长度。遍历一次 tokens。空间复杂度O(n)使用了一个辅助栈最坏情况下空间复杂度为 O(n)。
测试和验证
编写测试用例对算法进行验证确保其正确性和健壮性。
public class Main {public static void main(String[] args) {EvalRPN evalRPN new EvalRPN();String[] tokens1 {2,1,,3,*};System.out.println(evalRPN.evalRPN(tokens1)); // 9String[] tokens2 {4,13,5,/,};System.out.println(evalRPN.evalRPN(tokens2)); // 6String[] tokens3 {10,6,9,3,,-11,*,/,*,17,,5,};System.out.println(evalRPN.evalRPN(tokens3)); // 22}
}总结和拓展
本题通过使用栈来实现逆波兰表达式的求值利用栈的后进先出特性完成了计算。这个算法思路清晰简单在处理类似问题时是一个不错的选择。
除了当前算法我们也可以考虑其他实现方式例如使用队列、递归等方法来解决类似问题。
参考资料
《力扣经典150题》LeetCode 官方网站
