題目出處：https://zerojudge.tw/ShowProblem?problemid=k733
這是一個解析字串的題目，可以看作parser的一種
題目意思是這樣：你拿到一個磁帶，並且有一串碼說明讀取磁帶的順序。這串碼只有兩種指令，分別用T, L, E 三個字元代表：”到一個位置”、”重複(loop)動作直到看見E”。
例如：
- T10T15T23T23T22T22T44 代表你將從10出發，依序到15, 23, 23, 22, 22, 44的位置。
- T10T15T23T23T22T22T44 移動的距離為：5 + 8 + 0 + 1 + 0 + 22 = 36
- 題目要你計算整個過程一共移動了多少距離。
(這其實就是一個簡易的程式碼解析，只有To與Loop兩種動作)
解題關鍵想法：
- 如果沒有Loop 的情況，只要照着順序把字串轉爲數值，一邊累計距離即可
- 用一個index從1開始每次+3, 直到字串結束
- 但如有Loop，每遇到一個L 就把當時的資訊推進stack中，遇見一個E就讀出最後的數值。另外用一個stack紀錄次數，執行counter功能。每遇到一次E counter就-1; counter爲0的時候就可以pop stack
- 再想辦法優化程式（避免重複計算）
接下來有兩種解法，第一種很直白但會TLE。第二種是第一種的優化，其中省去了重複的動作，可AC
(TLE = Time Limit Exceeded; AC = Accepted 20筆側資全通過）
解法1: 直白的解法 (TLE)
雖然這樣寫會TLE, 但這還是主要的演算法邏輯與精神。用這張圖來說明
程式的流程
- 如果遇到T, 累加距離
- 用兩個stack, 分別紀錄 L開頭位置與次數。如果遇到L, 把當時的index與重複次數存下來
- 如果遇到E, 檢查另一個stack中的次數。如果重複次數減爲0, 就可以離開E，否則次數減一並且回到stack末端所指向的位置。
完整程式碼如下：
codes = input()
idx = 0
idx_stack = []
cnt_stack = [] # loop counter
ad = 0
pd = 10
while idx < len(codes):
if codes[idx]=='T':
v = int(codes[idx+1:idx+3])
ad += abs( v - pd)
pd = v
idx += 3
elif codes[idx]=='L':
looptimes = int(codes[idx+1])
cnt_stack.append(looptimes)
idx +=2
idx_stack.append(idx)
elif codes[idx]=='E': # reach the end of loop
if cnt_stack[-1] >1:
cnt_stack[-1] -=1
idx = idx_stack[-1]
else:
idx_stack = idx_stack[:-1]
cnt_stack = cnt_stack[:-1]
idx +=1
print(ad)解法2: 避免重複運算(AC)
關鍵：進入迴圈後的數值只要計算一次即可。進入迴圈前的位置p0, 進入迴圈後的第一個位置p1, 以及遇到E之前的最後一個位置pn記錄下來。
當遇到E的時候代表迴圈內容已經執行了一次，還有x-1次要執行。目前的累計距離 減去剛進入迴圈時的累計距離，大約就是在這個迴圈會增加的距離。記得扣掉 abs(p0-p1) 並且加上abs(pn-p1)才是是正確的”跑一圈會增加的距離”
完整程式碼
codes = input()
pd = 10
ad = 0
idx = 0
L = len(codes)
#stack_idx = []
stack_cnt = []
stack_p1 = []
stack_ad = []
stack_pd = []
while idx < L:
if codes[idx]=='T':
v = int(codes[idx+1:idx+3])
d = abs(pd - v)
pd = v
ad += d
if len(stack_p1)>0:
if stack_p1[-1] ==0:
stack_p1[-1] = v
ii = len(stack_p1)-2
while stack_p1[ii] == 0 and ii >=0:
stack_p1[ii] = stack_p1[ii+1]
ii-=1
idx +=3
elif codes[idx]=='L':
stack_p1.append(0)
x = int(codes[idx+1])
#stack_idx.append(idx+2)
stack_cnt.append(x)
stack_ad.append(ad)
stack_pd.append(pd)
idx += 2
elif codes[idx] =='E':
x1 = stack_cnt[-1]-1 # x-1
p01 = abs(stack_pd[-1] - stack_p1[-1])
pn1 = abs(stack_p1[-1] - pd)
ad_diff = ad - stack_ad[-1] - p01 + pn1
ad += x1*ad_diff
stack_p1.pop()
#stack_idx.pop()
stack_cnt.pop()
stack_ad.pop()
stack_pd.pop()
idx +=1
print(ad)
這題zerojudge上通過的比例比下一題還少，除了速度，在算法上優化更重要!
另一種解法是用遞迴的方式（話說程式的遞迴也是把program 位置存到stack裡面），改天再來寫～