[programming]Shunting Yard Algorithm

Shunting Yard (調車場)演算法，是可以把infix(算符中綴)表示法轉換成reverse polish(算符後綴)表示法。比如
這個中綴 (9*8)+(6/3)
變成
後綴 9 8 * 6 3 / +
反過來說，有沒有演算法是可以把 RPN (後綴) 轉成 Infix (中綴) 呢？

[programming]RedBlackTree

紅黑樹兩個條件

1. 兩個紅子不能互為親子
2. 由根(root)至每個葉(leaf)的路徑(path)上，黑子數相同

如果將[1,2,...15]共15個key插入紅黑樹，最後紅黑樹的外形，不會像是完美的(optimal)二元樹(Binary Search Tree)一樣是個對稱的金字塔。紅黑樹會變得左邊高度2，右邊高度5。



看起來好像不太好，你很怕[16.17.18]等key加上去，樹右方會無限制地變長。但實際上插入[16,17]後，樹右方仍只有5。




再加入[18]後，紅黑樹就開始左旋，讓左方分攤一節高度。右邊高度還是只有5。



因為有一、二的條件限制，樹左邊是3黑子，那樹右邊至多是[黑紅黑紅黑紅]，如果再繼續加上去的話，樹就會左旋，讓樹左邊分攤重量。

因此，紅黑樹的最長一邊(此例中為右邊)最多不會超過2⌈logN⌉，紅黑樹的search複雜度是在O(logN)。

紅黑樹跟一般的二元樹有何不同？

• 由於條件二，紅黑樹會算每一側的黑子數，所以不會過於偏斜

紅黑樹跟力求完美平衡的二元樹又有何不同？

• 紅黑樹允許紅子參雜在其中一側，而且只算黑子數，所以不會為了力平衡，使得旋轉次數太多。又由於條件一，避免兩個紅子互為親子，所以不會發生[黑紅紅紅紅...紅]的情況。

紅黑樹是平衡樹與一般二元樹的折衷之作，

[iPhone]iPhone耳機壞了

今天去健身中心一邊跑步一邊用iPhone聽音樂，汗水一直流沒時間擦汗。

回家坐公車想要用iPhone聽音樂時，我沒碰iPhone，但它竟然會自動跳到語音控制，亂撥電話給其他人，如果我把耳機拔掉後又正常了。

有可能是汗水弄濕，也有可能是收納線材時，捲上魚骨棒時捲壞的。

我現在想要買新耳機，可是怕原廠耳機會否因為被汗水淋濕而弄壞。有比較防水，但又有線控與麥克風功能的iPhone耳機嗎？

另一點是健身中心的跑步機會溢出靜電，跑步時如果不觸碰跑步機的金屬部份，靜電就會經由耳機傳到耳朵，耳朵一直被電。我想要跑步時把iPhone掛在手臂上，請問那種配件叫什麼？

[Puzzle]人過大佛寺*4=寺佛大過人，猜數字

Palindrome:
abcde*4 = edcba
[a,b,c,d,e] are five distinct decimal digits.

Use python to do brutal force searching:

#!/usr/bin/env python

revStr = lambda s:s[len(s)-1:0:-1]+s[0]
revInt = lambda n:int(revStr(str(n)))
isPalin = lambda a,b:revInt(a)==(b)
is4div = lambda n:n%4==0
biglist = range(1,99999)
quadMul = filter(is4div, biglist)
isQuoPalin = lambda n:isPalin(n/4,n)
blist = filter(isQuoPalin, quadMul)

"""
>>> print blist
[8712, 87912]
"""

The final answer is 87912/4 = 21978. So, 21978*4 = 87912.