字符串的求和
⽬录
实现字符串数字的减法
(1)
⼀、题⽬：将整数字符串转成整数值{python）
给定⼀个字符串str，如果str符合⽇常书写的整数形式，并且属于32位整数的范围，返回所代表的整数值，否则返回0。
eg
str = “123”，返回123.
str = “023”，因为“023”不符合⽇常的书写习惯，所以返回0.
str = “A23”，返回0；
str = “0”，返回0；
str= “2147483647”，返回2147483647.
str = “2147483648”，因为溢出了，所以返回0；
str = “-123”，返回-123；
思路：
空字符串输⼊、正负符号、⾮法字符、整型溢出【最难处理】
1. 检查⽇常书写，⾮法字符
第⼀个既不是负号，也不是数字的情况，如：‘A12’
第⼀个是负号，但是整个字符串的长度只有1，或者负号后⾯跟个0的情况，如‘-“或者”-012“
以0开头,⽽且整个字符串的长度⼤于1，如：‘012”
从第⼆个开始依次遍历字符串,⼀旦出现不是数字的情况⽴即返回FALSE
2. 字符转数字操作
字符串为空或者字符串的长度为0
字符串中存在不合法的字符
第⼀个字符是否为负号的情况
处理整数溢出：
当发⽣溢出时，取最⼤或最⼩的int值。即⼤于正整数能表⽰的范围时返回MAX_INT：2147483647；⼩于负整数能表⽰的范围时返回MIN_INT：-2147483648。
我们先设置⼀些变量：
sign⽤来处理数字的正负，当为正时sign > 0，当为负时sign < 0
n存放最终转换后的结果
c表⽰当前数字
处理溢出：
如果我们要转换的字符串是"2147483697"，那么当我扫描到字符'9'时，判断出214748369 > MAX_INT / 10 = 2147483647 / 10 = 214748364（C 语⾔⾥，整数相除⾃动取整，不留⼩数），则返回0；
如果我们要转换的字符串是"2147483648"，那么判断最后⼀个字符'8'所代表的数字8与MAX_INT % 10 = 7的⼤⼩，前者⼤，依然返回0。
代码：
#判断是否为合法
def isValid(s):
if s[0] != '-' and not s[0].isdigit():
return False
elif s[0] == '-' and (len(s) == 1 or s[1] == '0'):
return False
elif s[0] == '0' and len(s) > 1:
return False
for i in range(len(s)):
if not s[i].isdigit():
return False
return True
def convert(s):
#判断为空
if not s:
return 0
if not isValid(s):
return 0
sign = -1 if s[0] == '-' else 1
q = 214748364 #-2^31 // 10
maxr = 7
res , cur = 0 , 0
start = 0 if sign == 1 else 1
for i in range(start,len(s)):
cur = int(s[i])
if res > q or res == q and cur > maxr:
return 0
res = res * 10 + cur
if sign and res == 2147483648:
return 0
return res * sign
s = '2147483637'
convert(s)
⼆、字符串中数字⼦串的求和
　给定⼀个字符串str，求其中全部数字串所代表的数字之和
  1. 忽略⼩数点，“ A1.3 ” 表⽰的数字就是包含两个数字 1 和 3
  2. 紧贴数字的左边出现 “-”，其连续出现的数量如果为奇数，就视为负，如果为偶数，就视为正 “ A-1BC--23” 表⽰的是 -1 和 23思路：时间复杂度是O(N)，空间复杂度是O(1)
⾸先定义三个变量， res表⽰⽬前的累加和，num表⽰当前收集到的数字，布尔型变量flag表⽰将num加到res中，num是正还是负.代码：
def numSum(arr):
if not arr:
return 0
num , res = 0 , 0
flag = 1
i = 0
while i < len(arr):
while i < len(arr) and arr[i] == '-':
flag *= -1
i += 1
while i<len(arr) and arr[i].isdigit():
num = num*10 + int(arr[i])
i += 1
if i<len(arr) and not arr[i].isdigit():
i += 1
if num:
res += flag*num
num ,flag = 0 , 1
return res
arr = 'A1.3'
numSum(arr)
a="A-1BC--23"
numSum(a)
三、题⽬：公式字符串求值
思路：采⽤栈存储数字和加减符号，乘除在放⼊栈中已计算出结果。变量pre记录数字。括号就递归。
1、遇到数字：采⽤pre变量保存。
2、遇到符号：存⼊栈中，存⼊之前先把栈中的乘除结果算出来
3、遇到左括号：递归计算
4、遇到右括号：计算栈中的结果。
五、题⽬：基本计算器【只有 + ，- ，以及括号】
实现⼀个基本的计算器来计算⼀个简单的字符串表达式的值。
字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，⾮负整数和空格。
⽰例 1:
输⼊: "1 + 1"
输出: 2
⽰例 2:
输⼊: " 2-1 + 2 "
输出: 3
⽰例 3:
输⼊: "(1+(4+5+2)-3)+(6+8)"
输出: 23
⾮递归思路：
栈：
采⽤栈存储遇到（之前的结果。
遇到），将栈中最后⼀个数弹出计算结果。
处理过程：
res记录结果，stack⽤来存结果【遇到（）先存前⾯的结果】，sign记录符号+、-
1. 遇到 + ：sign = 1
2. 遇到 - ：sign = -1
3. 遇到数字：【考虑‘42’两个字母⼀起的情况，采⽤循环】结果 res  += int (42) * sign
4. 遇到 ’（ ’：stack中加⼊ res和sign
5. 遇到‘ ) ‘：stack弹出最后⼀个元素和倒数第⼆个元素来更新res
代码1：
def calculate(self, s):
"""
:type s: str
:rtype: int
"""
if not s:
return 0
#stack存储遇到括号（之前的计算结果res
#temp记录数字，【如‘42’两个数字⼀起出现的情况】
#sign记录符号+，-
#res记录计算结果
stack,temp = [],''
sign , res , i = 1 , 0 , 0
while i < len(s):
#遇到字母：如果有两个数字同时出现，采⽤循环解决
#res结果把符号相乘
if s[i].isdigit():
while i<len(s) and s[i].isdigit():
temp += s[i]
i += 1
i -= 1
res += int(temp)*sign
#遇到+，-，sign=1，-1
elif s[i] == '+':
sign = 1
elif s[i] == '-':
sign = -1
#遇到（，将前⾯的res和符号sign存⼊栈中，初始化res和sign
elif s[i] == '(':
stack.append(res)
stack.append(sign)
res,sign = 0,1
#遇到），将栈中原来的结果res和符号sign弹出和当前的res更新得到新的结果res
elif s[i] == ')':
if stack:
sign_tmp = stack.pop()
res_tmp = stack.pop()
res = res_tmp + res*sign_tmp
i += 1
temp= ''
return res
六、题⽬：基本计算器⼆【只有加减乘除，没有括号】实现⼀个基本的计算器来计算⼀个简单的字符串表达式的值。
字符串表达式仅包含⾮负整数，+， - ，*，/ 四种运算符和空格。整数除法仅保留整数部分。
⽰例 1:
输⼊: "3+2*2"
输出: 7
⽰例 2:
输⼊: " 3/2 "
输出: 1
⽰例 3:
输⼊: " 3+5 / 2 "
输出: 5
⾮递归思路1：
遇到数字：num存储
遇到符号：
字符串长度什么时候算01. +：栈存储：+num
2. -：栈存储：-num
3. *：num = 栈弹出最后⼀个元素 * num，再存⼊栈中
4. /：num = 栈弹出最后⼀个元素 / num，再存⼊栈中
如：'45/9'，先num = 45，然后45前⾯默认为+ 符号，将45存⼊栈中，然后 sign =  / ，num = 9，判断sign == '/'，将45弹出与num==9相除。
即每个数字与其前⾯的符号相对应，sign和num。
代码1：
def calculate(self, s):
if not s:
return "0"
stack, num, sign = [], 0, "+"
for i in range(len(s)):
if s[i].isdigit():
num = num*10+ord(s[i])-ord("0")
if (not s[i].isdigit() and not s[i].isspace()) or i == len(s)-1:
if sign == "-":
stack.append(-num)
elif sign == "+":
stack.append(num)
elif sign == "*":
stack.append(stack.pop()*num)
else:
tmp = stack.pop()
if tmp//num < 0 and tmp%num != 0:
stack.append(tmp//num+1)
else:
stack.append(tmp//num)
sign = s[i]
num = 0
return sum(stack)
⾮递归思路2：
栈：
遇到数字：就将数字存⼊栈中。【考虑两个数字⼀起出现的情况】
遇到 * 或 / 就将乘或者除计算结束再存⼊栈中。【其中还要考虑是数字的情况】
将栈最后⼀个元素弹出，然后与【乘号或者除号后⾯⼀个元素的数字】进⾏计算得到新的结果再存进栈中遇到加减，sign = 1或-1
结果：
将栈中所有元素加总就可以了
代码2：
def calculate(self, s):
"""
:type s: str
:rtype: int
"""
if not s:
return 0
# return eval(s)
stack = []
res,sign,i= 0,1,0

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。