題目:
實現(xiàn)一個基本的計算器來計算一個簡單的字符串表達(dá)式的值。
字符串表達(dá)式僅包含非負(fù)整數(shù)，+， - ，*，/ 四種運算符和空格??。 整數(shù)除法僅保留整數(shù)部分。
示例?1:
輸入: "3+2*2"
輸出: 7
示例 2:
輸入: " 3/2 "
輸出: 1
示例 3:
輸入: " 3+5 / 2 "
輸出: 5
說明：
你可以假設(shè)所給定的表達(dá)式都是有效的。
請不要使用內(nèi)置的庫函數(shù) eval
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/basic-calculator-ii
解題思路:
任何算法題,我們都可以假設(shè)最簡單的情況入手,寫一個簡單的框架出來,再逐步拓展復(fù)雜的情況,逐漸完善自己的算法
1.只考慮加減法情況,并且沒有括號,如s = “1+123”
設(shè)變量num=0,存放當(dāng)前數(shù)字,給它初始化為0,?這里它的變化過程是 0 1 123
變量sign=‘+’,存放當(dāng)前符號,并給他初始化為‘+’,這里它的變化過程是 ‘+’ ‘+’
變量stack=[]來存放結(jié)果,并初始化為空列表
2.遍歷s,當(dāng)碰到不同的情況將它的值放到上述不同的容器里
這里num有個難點,比如字符串‘123’遍歷是是1->2->3這樣進來的,怎么將它變成整型123?
如果只用int轉(zhuǎn)換,如果是一個巨大的數(shù)字,立馬就內(nèi)存溢出了,所以要循環(huán)遍歷 比如先進來1?
num = 0
num = 10*num+new num?
10*0 +1 = 1
10*1+2 = 12
10*12+3 = 123
3.數(shù)字的結(jié)果num 和運算符stack 計算完成后 添加到stack,最后只需要計算stack中的和就好了
if sign =='+':
stack.append(num)
elif sign =='-':
stack.append(-num)
4.補充
運算符乘法: 乘法等于上一個的值乘以下一個的值,所以取stack[-1]*num
運算符出發(fā): 乘法等于上一個的值整除(這道題不考慮小數(shù))下一個的值,所以取stack[-1] //num
括號:
因為括號具有遞歸性質(zhì)。我們拿字符串3*(4-5/2)-6舉例：
calculate(3*(4-5/2)-6)
= 3 * calculate(4-5/2) - 6
= 3 * 2 - 6
= 0
可以腦補一下，無論多少層括號嵌套，通過 calculate 函數(shù)遞歸調(diào)用自己，都可以將括號中的算式化簡成一個數(shù)字。換句話說，括號包含的算式，我們直接視為一個數(shù)字就行了。
現(xiàn)在的問題是，遞歸的開始條件和結(jié)束條件是什么？遇到(開始遞歸，遇到)結(jié)束遞歸
完整的代碼:
def calculate(s:str) ->int:
def helper(s: List) ->int:
stack = []
sign ='+'
? ? ? ? num =0
? ? ? ? while len(s) >0:
c = s.pop(0)
if c.isdigit():
num =10 * num +int(c)
if (not c.isdigit()and c !=' ')or len(s) ==0:
if sign =='+':
stack.append(num)
elif sign =='-':
stack.append(-num)
elif sign =='*':
stack[-1] = stack[-1] * num
elif sign =='/':
# python 除法向 0 取整的寫法
? ? ? ? ? ? ? ? ? ? stack[-1] =int(stack[-1] /float(num))
num =0
? ? ? ? ? ? ? ? sign = c
return sum(stack)
# 需要把字符串轉(zhuǎn)成列表方便操作
? ? return helper(list(s))
