Leetcode|Leetcode 基本计算器
文章图片
WechatIMG579.jpeg 题目描述
leetcode 第224题：基本计算器解题方法
实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。
示例：
输入：s = " (1+(4+5+2)-3)+(6+8) "
输出：23
栈
参照题解
- 解题思路
【Leetcode|Leetcode 基本计算器】由于字符串表达式s中存在空格，需要先去除空格，这时s中仅存在数字、加减号、括号
将s整体转换为加法运算，减去一个数可以理解为加上这个数的负数，1-1看作1+(-1)
然后定义变量sign来标示每个数前面的正负符号{-1,+1}
对于s，第一个数前面的符号一定为正，1-1看作0+1-1，所以sign默认为1并压栈
定义变量sumS，存储s计算后的值，初始为0
获取s的长度n，在[0,n)的范围内循环得到当前字符s[i]
如果s[i]为+号，则更新sign为栈顶元素
如果s[i]为-号，则更新sign为栈顶元素的负数
如果s[i]为（号，将当前的sign压栈
如果s[i]为）号，弹出栈顶元素
如果s[i]为数字，sumS累加当前数字的数值sign*num
最后s计算后的值就是sumS
- 复杂度
时间复杂度：O(n)，n为字符串s的长度
空间复杂度：O(n)，n为字符串s的长度
- 代码实现
python3
class Solution:
def calculate(self, s: str) -> int:
s = s.replace(" ","")
n = len(s)
sign = 1
stack = [sign]
i = sumS = 0
while iphp
class Solution {
function calculate($s) {
$s = str_replace(" ","",$s);
$n = strlen($s);
$sign = 1;
$stack = [$sign];
$i = $sumS = 0;
while($i<$n){
if($s[$i]=="+"){
$sign = end($stack);
$i++;
}elseif($s[$i]=="-"){
$sign = -end($stack);
$i++;
}elseif($s[$i]=="("){
array_push($stack,$sign);
$i++;
}elseif($s[$i]==")"){
array_pop($stack);
$i++;
}else{
$num = 0;
while($i<$n && is_numeric($s[$i])){
$num = $num*10+$s[$i];
$i++;
}
$sumS += $sign*$num;
}
}
return $sumS;
}
}
推荐阅读
- 做一件事情的基本原理是什么（）
- dubbo基本认识
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- HTML基础--基本概念--跟着李南江学编程
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 7、前端--jQuery简介、基本选择器、基本筛选器、属性选择器、表单选择器、筛选器方法、节点操作、绑定事件
- LeetCode（03）Longest|LeetCode（03）Longest Substring Without Repeating Characters
- 一般模型化关系——从模型是什么到如何起作用的基本答案