字符串的求和
目錄
- 將整數字符串轉成整數值{python）
- 字符串中數字子串的求和
- 公式字符串求值
- 實現字符串數字的減法
- 基本計算器(1)
- 基本計算器（2）
- 基本計算器（3）
一、題目：將整數字符串轉成整數值{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 Falseelif s[0] == '-' and (len(s) == 1 or s[1] == '0'):return Falseelif s[0] == '0' and len(s) > 1:return Falsefor i in range(len(s)):if not s[i].isdigit():return Falsereturn True def convert(s):#判斷為空if not s:return 0if not isValid(s):return 0sign = -1 if s[0] == '-' else 1q = 214748364 #-2^31 // 10maxr = 7res , cur = 0 , 0 start = 0 if sign == 1 else 1for i in range(start,len(s)): cur = int(s[i])if res > q or res == q and cur > maxr:return 0res = res * 10 + cur if sign and res == 2147483648:return 0return 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 0num , res = 0 , 0flag = 1i = 0while i < len(arr):while i < len(arr) and arr[i] == '-':flag *= -1i += 1while i<len(arr) and arr[i].isdigit():num = num*10 + int(arr[i])i += 1if i<len(arr) and not arr[i].isdigit():i += 1if num:res += flag*num num ,flag = 0 , 1return 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：
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 += 1i -= 1res += int(temp)*sign #遇到+，-，sign=1，-1elif s[i] == '+':sign = 1elif s[i] == '-':sign = -1 #遇到（，將前面的res和符號sign存入棧中，初始化res和signelif s[i] == '(':stack.append(res)stack.append(sign)res,sign = 0,1 #遇到），將棧中原來的結果res和符號sign彈出和當前的res更新得到新的結果reselif s[i] == ')':if stack:sign_tmp = stack.pop()res_tmp = stack.pop()res = res_tmp + res*sign_tmpi += 1temp= ''return res六、題目：基本計算器二【只有加減乘除，沒有括號】
實現一個基本的計算器來計算一個簡單的字符串表達式的值。
字符串表達式僅包含非負整數，+， - ，*，/ 四種運算符和空格??。 整數除法僅保留整數部分。
示例?1:
輸入: "3+2*2" 輸出: 7示例 2:
輸入: " 3/2 " 輸出: 1示例 3:
輸入: " 3+5 / 2 " 輸出: 5非遞歸思路1：
- 遇到數字：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,0num = ''ca = Truewhile i < len(s):ss = s[i] #數字，考慮兩個數字出現的情況，用循環if ss.isdigit():while i<len(s) and s[i].isdigit():num += s[i]i += 1ca = Falsestack.append(int(num)*sign) #加減sign = 1或者-1elif ss == '+':sign = 1elif ss == '-':sign = -1 #乘號，elif ss == '*':#可能后面是空白符號while not s[i].isdigit():i += 1#考慮兩個數字一起出現while i<len(s) and s[i].isdigit():num += s[i]i += 1ca = False#將棧最后一個元素和乘號*后面一個數字相乘res = stack.pop() * int(num)#將結果存入棧中stack.append(res) #除號elif ss == '/':value = stack.pop()while not s[i].isdigit():i += 1while i<len(s) and s[i].isdigit():num += s[i]i += 1ca = False#m是用來限制除法取整的，如果除的結果是負數，則結果要加1，正數不用m = value//int(num)if value % int(num) != 0:m += 1 if m < 0 else 0#將除的結果加入棧中res = int(m)stack.append(res)if ca:i += 1num , ca = '',Truereturn sum(stack)?
七、題目：基本計算器三【既有乘除又有括號】
?
這道題將一和二結合，就是遇到括號就遞歸，別的就都與題目二一樣。
思路：采用棧存儲數字和加減符號，乘除在放入棧中已計算出結果。變量pre記錄數字。括號就遞歸。
1、遇到數字：采用pre變量保存。
2、遇到符號：存入棧中，存入之前先把棧中的乘除結果算出來
3、遇到左括號：遞歸計算
4、遇到右括號：計算棧中的結果。
def getValue(s):if not s:return 0return value(list(s),0)[0] #遞歸函數，遇到左括號 def value(arr,i):deque = []pre = 0while 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 += 1pre = 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 / predeque.append(pre) #加減法計算 def addNum(deque):res = 0sign = 1while deque:cur = deque.pop(0)if cur == '-':sign = -1elif cur == '+':sign = 1else:res += sign * int(cur)return res exp = '48*((70-65)-43)+8*1*3+5/5' getValue(exp)?
轉載于:https://www.cnblogs.com/Lee-yl/p/10462757.html
總結
- 上一篇： 2019.3.2 区块链论文翻译
- 下一篇： AI大神贾扬清确认将离开Facebook