怎么查找网站是谁做的,如何让网站给百度收录,输入法网站设计,山东教育网站开发公司#x1f4d6;逆波兰表达式求值 ✅描述✅扩展#xff1a;什么是逆波兰表达式✅题解方法一#xff1a;栈✅题解方法二#xff08;数组模拟栈#xff09; 今天又刷了一道题#xff0c;奥利给 刷题地址#xff1a;
点击跳转 ✅描述
给定一个逆波兰表达式#xff0c;求表达… 逆波兰表达式求值 ✅描述✅扩展什么是逆波兰表达式✅题解方法一栈✅题解方法二数组模拟栈 今天又刷了一道题奥利给 刷题地址
点击跳转 ✅描述
给定一个逆波兰表达式求表达式的值。
数据范围表达式长度满足 1≤≤104 1≤n≤104 表达式中仅包含数字和 - , * , / 其中数字的大小满足 ∣∣≤200 ∣val∣≤200 。
示例1
输入
[2,1,,4,*]返回值
12示例2
输入
[2,0,]返回值
2✅扩展什么是逆波兰表达式
表达式一般由操作数(Operand)、运算符(Operator)组成例如算术表达式中通常把运算符放在两个操作数的中间这称为中缀表达式(Infix Expression)如AB。
波兰数学家Jan Lukasiewicz提出了另一种数学表示法它有两种表示形式
把运算符写在操作数之前称为波兰表达式(Polish Expression)或前缀表达式(Prefix Expression)如AB把运算符写在操作数之后称为逆波兰表达式(Reverse Polish Expression)或后缀表达式(Suffix Expression)如AB前后缀表达式的出现是为了方便计算机处理它的运算符是按照一定的顺序出现所以求值过程中并不需要使用括号来指定运算顺序也不需要考虑运算符号比如加减乘除的优先级。
先介绍中简单的人工转化方法
假设有一个中缀表达式ab*c-(de)
首先将这个中缀表达式的所有运算加括号((a(b*c))-(de))然后将所有运算符放到括号后面这样就变成了((a(bc)* ) (de) )-把所有括号去掉abc*de±最后得出的结果就是后缀表达式。
✅题解方法一栈
具体做法
逆波兰表达式可以看成一种后序表达式只需要在遇到符号的时候计算它前面两个数字即可因此可以使用栈的先进后出原理。
遍历整个字符串数组遇到数字就将其从字符串转变成int数字然后加入栈中等待计算。遇到符号先取出栈中最后一位然后与取出后的最后一位计算结果存入最后一位如下图所示 public int evalRPN (String[] tokens) {StackInteger stack new Stack();for (int i 0; i tokens.length; i) {if (tokens[i].equals() || tokens[i].equals(-) || tokens[i].equals(*) || tokens[i].equals(/)) {if (tokens[i].equals()) {stack.push(stack.pop() stack.pop());}else if (tokens[i].equals(-)) {stack.push(-stack.pop() stack.pop());}else if (tokens[i].equals(*)) {stack.push(stack.pop() * stack.pop());}else if (tokens[i].equals(/)) {int a stack.pop();int b stack.pop();stack.push(b / a);}}else {stack.push(Integer.parseInt(tokens[i]));}}return stack.pop();}复杂度分析
时间复杂度()O(n)遍历整个字符串数组空间复杂度()O(n)栈空间最大为数组长度即全是数字
✅题解方法二数组模拟栈
与方法一的思路差不多不过可以考虑使用数组来模拟栈。 假设逆波兰表达式中总共有n个元素则n必定是奇数并且数字的个数恰好比运算符个数多1。因为起初只有1个数字时每加一个运算符必定会加1个数字依次类推数字恰好比运算符多1。所以数字个数有(1)/2(n1)/2个运算符个数有(−1)/2(n−1)/2个。用栈模拟的过程中每次遇到数字直接压入栈中栈的容量会加1遇到运算符时先弹出两个元素做运算后再压入栈中栈的容量会减1。最坏情况下数字全在前面运算符全在后面栈的容量最多达到(1)/2(n1)/2。 我们初始化arr数组的容量为(1)/2(n1)/2。用一个变量index指向栈顶的位置index为-1表示栈容量为0。当压栈时index加1再将元素赋给当前位置弹栈时index减1即可。
public int evalRPN (String[] tokens) {int n tokens.length;int[] arr new int[(n1)/2];int index -1;for (String token : tokens) {if (!(token.equals() || token.equals(-) || token.equals(*) || token.equals(/))){arr[index] Integer.parseInt(token);}else {if (token.equals()){index--;arr[index] arr[index1];}else if (token.equals(-)){index--;arr[index] - arr[index1];}else if (token.equals(*)){index--;arr[index] * arr[index1];}else if (token.equals(/)){index--;arr[index] / arr[index1];}}}return arr[0];}
