2018新网站做外链,app制作的网站,兴平做网站,网站建设方案2018一、题目描述
给你一个字符串表达式 s #xff0c;请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-2^31, 2^31 - 1] 的范围内。
注意#xff1a;不允许使用任何将字符串作为数学表达式计算…一、题目描述
给你一个字符串表达式 s 请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-2^31, 2^31 - 1] 的范围内。
注意不允许使用任何将字符串作为数学表达式计算的内置函数比如 eval() 。 示例 1
输入s 32*2
输出7示例 2
输入s 3/2
输出1示例 3
输入s 35 / 2
输出5提示
1 s.length 3 * 10^5s 由整数和算符 (, -, *, /) 组成中间由一些空格隔开s 表示一个 有效表达式表达式中的所有整数都是非负整数且在范围 [0, 2^31 - 1] 内题目数据保证答案是一个 32-bit 整数
二、解题思路
这个问题可以使用栈stack来解决。我们使用两个栈一个用于存储操作数另一个用于存储操作符。遍历字符串s根据遇到的字符类型数字、操作符或空格进行相应的处理。
当遇到数字时将其转换为整数并存储在操作数栈中。当遇到操作符时需要考虑操作符的优先级。如果当前操作符的优先级高于栈顶操作符的优先级则直接将当前操作符入栈。否则需要先计算栈顶的操作符并将结果重新入栈然后比较当前操作符与新的栈顶操作符的优先级。当遇到空格时忽略它。对于乘法和除法因为它们的优先级高于加法和减法所以一旦遇到乘号或除号需要立即计算结果并将结果入栈。对于加法和减法可以直接将操作数入栈因为它们可以在最后一起计算。
以下是具体的步骤
初始化两个栈一个用于存储操作数nums另一个用于存储操作符ops。遍历字符串s对于每个字符c 如果c是空格则忽略。如果c是数字则解析出完整的数字并压入nums栈。如果c是操作符、-、*、/ 如果ops栈为空或者栈顶的操作符是(则直接将c压入ops栈。如果c是*或/则从nums栈中弹出两个操作数进行计算并将结果压回nums栈。如果c是或-并且ops栈顶不是(则从nums栈中弹出两个操作数进行计算并将结果压回nums栈然后将c压入ops栈。遍历完成后如果ops栈中还有操作符则继续从nums栈中弹出操作数进行计算直到ops栈为空。最后nums栈中的唯一元素即为表达式的结果。
三、具体代码
import java.util.Stack;public class Solution {public int calculate(String s) {StackInteger nums new Stack();StackCharacter ops new Stack();for (int i 0; i s.length(); i) {char c s.charAt(i);if (c ) continue;if (Character.isDigit(c)) {int num 0;while (i s.length() Character.isDigit(s.charAt(i))) {num num * 10 (s.charAt(i) - 0);i;}i--; // since the for loop also increments inums.push(num);} else if (c () {ops.push(c);} else if (c )) {while (ops.peek() ! () {nums.push(applyOp(ops.pop(), nums.pop(), nums.pop()));}ops.pop();} else if (c || c - || c * || c /) {while (!ops.isEmpty() hasPrecedence(c, ops.peek())) {nums.push(applyOp(ops.pop(), nums.pop(), nums.pop()));}ops.push(c);}}while (!ops.isEmpty()) {nums.push(applyOp(ops.pop(), nums.pop(), nums.pop()));}return nums.pop();}public boolean hasPrecedence(char op1, char op2) {if (op2 ( || op2 )) return false;if ((op1 * || op1 /) (op2 || op2 -)) return false;return true;}public int applyOp(char op, int b, int a) {switch (op) {case : return a b;case -: return a - b;case *: return a * b;case /: return a / b;}return 0;}
}请注意代码中的applyOp方法假设栈中的操作数顺序是正确的并且对于减法和除法a和b的顺序很重要a是被操作数b是操作数。代码也处理了括号的情况确保在遇到右括号时所有括号内的表达式都会被计算。
四、时间复杂度和空间复杂度
1. 时间复杂度
遍历字符串s假设字符串s的长度为n则遍历字符串的时间复杂度为O(n)。解析数字在遍历过程中每次遇到数字需要解析出完整的数字。在最坏的情况下数字可能连续出现这意味着对于每个数字字符我们需要进行一次操作。因此解析数字的总操作次数也是O(n)。应用操作符在遍历字符串的过程中每次遇到操作符我们可能需要从栈中弹出元素进行计算然后将结果压回栈中。在最坏的情况下可能需要对每个操作符都进行这样的操作。由于每个操作符最多被处理一次因此这一步的时间复杂度也是O(n)。
综上所述总的时间复杂度为O(n)其中n是字符串s的长度。
2. 空间复杂度
操作数栈nums在最坏的情况下所有数字都直接入栈没有进行任何计算因此栈的大小可能达到O(n)。操作符栈ops在最坏的情况下所有操作符都直接入栈没有进行任何计算因此栈的大小可能达到O(n)。
综上所述总的空间复杂度为O(n)其中n是字符串s的长度。
这里的O(n)表示算法的复杂度与输入字符串的长度成线性关系。在实际情况中由于数字不会连续占据整个字符串操作符栈和操作数栈的大小通常会小于n但最坏情况下的复杂度分析仍然是O(n)。
五、总结知识点 栈Stack的使用 栈是一种后进先出Last In First Out, LIFO的数据结构。在Java中Stack类是java.util包中的一个类用于实现栈数据结构。 字符和字符串操作 使用char类型来处理单个字符。使用String类的charAt方法来获取字符串中指定位置的字符。使用Character.isDigit方法来判断一个字符是否是数字。 数字解析 通过循环和字符减去’0’的方式将字符串中的连续数字字符转换为整数。 运算符优先级 在处理算术表达式时需要根据运算符的优先级来决定计算的顺序。使用hasPrecedence方法来判断当前运算符与栈顶运算符的优先级关系。 条件逻辑 使用if-else语句来处理不同类型的字符空格、数字、运算符、括号。使用while循环来处理连续的数字字符以及应用运算符。 异常处理 虽然在给出的代码中没有显示异常处理但在实际应用中应当考虑除法操作可能导致的ArithmeticException如除以零。 递归下降 在处理括号时实际上隐式地使用了递归下降解析的原理通过递归地将括号内的表达式视为一个子表达式来处理。 运算符应用 使用applyOp方法来根据运算符执行相应的算术运算。 算法逻辑 理解和实现一个基本的算术表达式求值算法这涉及到算法设计的基本概念。 类型转换 在将字符转换为整数时涉及到从char到int的类型转换。
以上就是解决这个问题的详细步骤希望能够为各位提供启发和帮助。
