企业网站 用个人备案,wordpress 360急速模式打不开,什么样的蓝色做网站做好看,问卷调查微信小程序怎么做优质博文#xff1a;IT-BLOG-CN
一、题目
给你一个字符串表达式s#xff0c;请你实现一个基本计算器来计算并返回它的值。注意:不允许使用任何将字符串作为数学表达式计算的内置函数#xff0c;比如eval()。
示例 1#xff1a; 输入#xff1a;s 1 1 输出…优质博文IT-BLOG-CN
一、题目
给你一个字符串表达式s请你实现一个基本计算器来计算并返回它的值。注意:不允许使用任何将字符串作为数学表达式计算的内置函数比如eval()。
示例 1 输入s 1 1 输出2
示例 2 输入s 2-1 2 输出3
示例 3 输入s (1(452)-3)(68) 输出23 1 s.length 3 * 105 s由数字、、-、(、)和 ’ ’ 组成 s表示一个有效的表达式 不能用作一元运算(例如 1和(2 3)无效) -可以用作一元运算(即-1和-(2 3)是有效的) 输入中不存在两个连续的操作符 每个数字和运行的计算将适合于一个有符号的32位整数 二、代码
括号展开 栈 由于字符串除了数字与括号外只有加号和减号两种运算符。因此如果展开表达式中所有的括号则得到的新表达式中数字本身不会发生变化只是每个数字前面的符号会发生变化。因此我们考虑使用一个取值为{−1,1}的整数sign代表「当前」的符号。根据括号表达式的性质它的取值 【1】与字符串中当前位置的运算符有关 【2】如果当前位置处于一系列括号之内则也与这些括号前面的运算符有关每当遇到一个以−号开头的括号则意味着此后的符号都要被「翻转」。
考虑到第二点我们需要维护一个栈ops其中栈顶元素记录了当前位置所处的每个括号所「共同形成」的符号。例如对于字符串12(3-(45)) 【1】扫描到12时由于当前位置没有被任何括号所包含则栈顶元素为初始值1 【2】扫描到12(3时当前位置被一个括号所包含该括号前面的符号为号因此栈顶元素依然1 【3】扫描到12(3-(4时当前位置被两个括号所包含分别对应着号和−号由于号和−号合并的结果为−号因此栈顶元素变为−1。
在得到栈ops之后sign的取值就能够确定了如果当前遇到了号则更新sign←ops.top()如果遇到了遇到了−号则更新sign←−ops.top()。然后每当遇到(时都要将当前的sign取值压入栈中每当遇到)时都从栈中弹出一个元素。这样我们能够在扫描字符串的时候即时地更新ops中的元素。
class Solution {public int calculate(String s) {DequeInteger ops new LinkedListInteger();ops.push(1);int sign 1;int ret 0;int n s.length();int i 0;while (i n) {if (s.charAt(i) ) {i;} else if (s.charAt(i) ) {sign ops.peek();i;} else if (s.charAt(i) -) {sign -ops.peek();i;} else if (s.charAt(i) () {ops.push(sign);i;} else if (s.charAt(i) )) {ops.pop();i;} else {long num 0;while (i n Character.isDigit(s.charAt(i))) {num num * 10 s.charAt(i) - 0;i;}ret sign * num;}}return ret;}
}时间复杂度 O(n)其中n为字符串s的长度。需要遍历字符串s一次计算表达式的值。 空间复杂度 O(n)其中n为字符串s的长度。空间复杂度主要取决于栈的空间栈中的元素数量不超过n。
