网站是什么样子的,无极在线房屋出租信息,延吉手机网站建设开发,服装定制行业市场分析给你一个字符串表达式 s #xff0c;请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意#xff1a;不允许使用任何将字符串作为数学表达式计算的内置函数#…给你一个字符串表达式 s 请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意不允许使用任何将字符串作为数学表达式计算的内置函数比如 eval() 。
示例 1 输入s “32*2” 输出7 示例 2
输入s 3/2 输出1 示例 3
输入s 35 / 2 输出5 栈
class Solution {
public:int calculate(string s) {stackint st;int i 0;int n s.size();char preSign ;while(i n){if(s[i] ){i;continue;}long long num 0;while(i n s[i] 0 s[i] 9){num num * 10 s[i] - 0;i;}if (i n || !isdigit(s[i])) {if(preSign ){st.push(num);}else if(preSign -){st.push(-num);}else if(preSign /){int t st.top() / num;st.pop();st.push(t);}else if(preSign *){int t st.top() * num;st.pop();st.push(t);}preSign s[i];num 0;}i;}int res 0;while(!st.empty()){res st.top();st.pop();}return res;}
};时间复杂度和空间复杂度双O(N)
这道题我们要解决的问题就是我们需要先计算乘和除那么我们就可以使用栈当遇到符号是加号或者减号的时候推入num或者-num到栈中然后遇到乘号或者除号就在栈顶上进行运算。
然后我们定义一个preSign来储存计算的符号当遍历到加减乘除的时候我们会将当前符号前面的num与栈顶的元素进行运算。举个例子输入s 35 / 2 那么当我们遍历3的时候会被储存在num中当遇到加号的时候就会将num给push到栈中然后将preSign更新为加号然后遍历到5记录到num中然后空格跳过接下来遇到除号我们这时候不进行除号运算而是进行前面preSign的运算preSign是加号也就是继续将5推入栈中运算完后将preSign更新为除号然后遍历2记录num2这时候经过while循环的i此时in触发了if判断此时preSign为除号将栈顶的5除以当前的num值2。
最后我们只需要将栈中所有元素加起来即可最终运算结果是5。
