凡科网站建设怎么去掉极速建站,茂名网络推广,芷江建设工程招投标网站,一份电子商务网站建设规划书优质博文#xff1a;IT-BLOG-CN
一、题目
给你一个字符串数组tokens#xff0c;表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。 有效的算符为 ‘’、‘-’、‘*’ 和 ‘/’ 。 每个操作数#xff08;运算对象#xff09;都…优质博文IT-BLOG-CN
一、题目
给你一个字符串数组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) 5 17 5 22 1 tokens.length 104 tokens[i]是一个算符“”、“-”、“*” 或 “/”或是在范围[-200, 200]内的一个整数 逆波兰表达式由波兰的逻辑学家卢卡西维兹提出。逆波兰表达式的特点是没有括号运算符总是放在和它相关的操作数之后。因此逆波兰表达式也称后缀表达式。
二、代码
【1】栈 逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时使用一个栈存储操作数从左到右遍历逆波兰表达式进行如下操作如果遇到操作数则将操作数入栈如果遇到运算符则将两个操作数出栈其中先出栈的是右操作数后出栈的是左操作数使用运算符对两个操作数进行运算将运算得到的新操作数入栈。整个逆波兰表达式遍历完毕之后栈内只有一个元素该元素即为逆波兰表达式的值。
class Solution {public int evalRPN(String[] tokens) {DequeInteger stack new LinkedListInteger();int n tokens.length;for (int i 0; i n; i) {String token tokens[i];if (isNumber(token)) {stack.push(Integer.parseInt(token));} else {int num2 stack.pop();int num1 stack.pop();switch (token) {case :stack.push(num1 num2);break;case -:stack.push(num1 - num2);break;case *:stack.push(num1 * num2);break;case /:stack.push(num1 / num2);break;default:}}}return stack.pop();}public boolean isNumber(String token) {return !(.equals(token) || -.equals(token) || *.equals(token) || /.equals(token));}
}时间复杂度 O(n)其中n是数组tokens的长度。需要遍历数组tokens一次计算逆波兰表达式的值。 空间复杂度 O(n)其中n是数组tokens的长度。使用栈存储计算过程中的数栈内元素个数不会超过逆波兰表达式的长度。
【2】数组模拟栈 方法一使用栈存储操作数。也可以使用一个数组模拟栈操作。如果使用数组代替栈则需要预先定义数组的长度。对于长度为n的逆波兰表达式显然栈内元素个数不会超过n但是将数组的长度定义为n仍然超过了栈内元素个数的上界。那么栈内元素最多可能有多少个
对于一个有效的逆波兰表达式其长度n一定是奇数且操作数的个数一定比运算符的个数多1个即包含(n1)/2个操作数和(n−1)/2个运算符。考虑遇到操作数和运算符时栈内元素个数分别会如何变化 1、如果遇到操作数则将操作数入栈因此栈内元素增加1个 2、如果遇到运算符则将两个操作数出栈然后将一个新操作数入栈因此栈内元素先减少2个再增加1个结果是栈内元素减少1个。
由此可以得到操作数和运算符与栈内元素个数变化的关系遇到操作数时栈内元素增加1个遇到运算符时栈内元素减少1个。
最坏情况下n1)/2个操作数都在表达式的前面(n−1)/2个运算符都在表达式的后面此时栈内元素最多为(n1)/2个。在其余情况下栈内元素总是少于(n1)/2个。因此在任何情况下栈内元素最多可能有(n1)/2个将数组的长度定义为(n1)/2即可。
具体实现方面创建数组stack模拟栈数组下标0的位置对应栈底定义index表示栈顶元素的下标位置初始时栈为空index−1。当遇到操作数和运算符时进行如下操作 1、如果遇到操作数则将index的值加1然后将操作数赋给stack[index] 2、如果遇到运算符则将index的值减1此时stack[index]和stack[index1]的元素分别是左操作数和右操作数使用运算符对两个操作数进行运算将运算得到的新操作数赋给stack[index]。
整个逆波兰表达式遍历完毕之后栈内只有一个元素因此index0此时stack[index]即为逆波兰表达式的值。
class Solution {public int evalRPN(String[] tokens) {int n tokens.length;int[] stack new int[(n 1) / 2];int index -1;for (int i 0; i n; i) {String token tokens[i];switch (token) {case :index--;stack[index] stack[index 1];break;case -:index--;stack[index] - stack[index 1];break;case *:index--;stack[index] * stack[index 1];break;case /:index--;stack[index] / stack[index 1];break;default:index;stack[index] Integer.parseInt(token);}}return stack[index];}
}时间复杂度 O(n)其中n是数组tokens的长度。需要遍历数组tokens一次计算逆波兰表达式的值。 空间复杂度 O(n)其中n是数组tokens的长度。需要创建长度为(n1)/2的数组模拟栈操作。
