目录
- 实现字符串数字的减法
- (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；思路：
空字符串输入、正负符号、非法字符、整型溢出【最难处理】
- 检查日常书写，非法字符
- 第一个既不是负号,也不是数字的情况，如：‘A12’
- 第一个是负号,但是整个字符串的长度只有1,或者负号后面跟个0的情况，如‘-“或者”-012“
- 以0开头,而且整个字符串的长度大于1，如：‘012”
- 从第二个开始依次遍历字符串,一旦出现不是数字的情况立即返回FALSE
- 字符转数字操作
-
- 字符串为空或者字符串的长度为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 Truedef 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 * signs = '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
三、题目：公式字符串求值
思路：采用栈存储数字和加减符号，乘除在放入栈中已计算出结果。变量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记录符号+、-
- 遇到 + ：sign = 1
- 遇到 - ：sign = -1
- 遇到数字：【考虑‘42’两个字母一起的情况，采用循环】结果 res += int (42) * sign
- 遇到 ’（ ’：stack中加入 res和sign
- 遇到‘ ) ‘：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
六、题目：基本计算器二【只有加减乘除，没有括号】
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。
示例 1:
输入: "3+2*2"输出: 7
示例 2:
输入: " 3/2 "输出: 1
示例 3:
输入: " 3+5 / 2 "输出: 5
非递归思路1：
- 遇到数字：num存储
- 遇到符号：
- +：栈存储：+num
- -：栈存储：-num
- *：num = 栈弹出最后一个元素 * num，再存入栈中
- /：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 num = '' ca = True while i < len(s): ss = s[i]#数字，考虑两个数字出现的情况，用循环 if ss.isdigit(): while i
七、题目：基本计算器三【既有乘除又有括号】
这道题将一和二结合，就是遇到括号就递归，别的就都与题目二一样。
思路：采用栈存储数字和加减符号，乘除在放入栈中已计算出结果。变量pre记录数字。括号就递归。
1、遇到数字：采用pre变量保存。
2、遇到符号：存入栈中，存入之前先把栈中的乘除结果算出来
3、遇到左括号：递归计算
4、遇到右括号：计算栈中的结果。
def getValue(s): if not s: return 0 return value(list(s),0)[0]#递归函数，遇到左括号def value(arr,i): deque = [] pre = 0 while i < len(arr) and arr[i] != ')': #如果是数字，用pre变量保存 if arr[i].isdigit(): pre = pre * 10 + int(arr[i]) i += 1 #如果是符号，加入栈中，但先要把栈中的乘除结果算出来。 elif arr[i] != '(': mulNum(deque,pre) deque.append(arr[i]) i += 1 pre = 0 #如果是左括号（，就递归。 else: bra = value(arr,i+1) pre = bra[0] i = bra[1] + 1 #如果是右括号）或者结束了，就求出最终结果。 mulNum(deque,pre) return [addNum(deque),i]#乘除法计算 def mulNum(deque,pre): if deque: last = deque.pop() if last == '+' or last == '-': deque.append(last) else: cur = int(deque.pop()) pre = pre * cur if last == '*' else cur / pre deque.append(pre)#加减法计算def addNum(deque): res = 0 sign = 1 while deque: cur = deque.pop(0) if cur == '-': sign = -1 elif cur == '+': sign = 1 else: res += sign * int(cur) return resexp = '48*((70-65)-43)+8*1*3+5/5'getValue(exp)