[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.

[bus]懷疑指南客運905公車誘騙乘客多刷一段票

我從大鵬一村搭乘指南客運905公車，這時燈號是「上車收票」，我刷卡，司機沒有給我段票證明。

在忠孝敦化站下車時，燈號變成「下車收票」，實際上我不刷票也可以，我刷了票司機也不會提醒說多收了我一段票，也不會退還給我錢。

從905路線圖來看，大鵬一村正好是分段點，從這裡上車到忠孝敦化應該只有一段票才對。

其他公車是怎麼做的？在大鵬一村搭乘906、909的話，燈號是「上車收票」，刷了卡後司機會給段票證明，之後過了橋燈號變為「下車收票」，下車就交段票證明。

我懷疑的是，905公車可能是故意取巧，不給你段票證明，誘騙你以為是兩段票，多收了錢也不會提醒你。

[Gratitude to WorldGym]感謝加州運動中心把我趕出來

去年六月時，我為了自身的健康著想，去靠近公司的東區ATT頂好附近的加州運動中心。想說一個月二千多元好像很划算，刷完卡後，一個女性主管跑來跟我說，我的性別不適當，他們無法接收我當會員，把我的錢退還給我。

當時覺得這樣被人拒絕好像是種羞辱，很想哭又不想表現出給他們看。在街頭流浪了許久，發現到八德路上的松山運動中心，只要五十元就可以進去用一小時。他們不管你是男是女是偽娘是扶他，只要繳交了五十元就可進去健身中心。我最須要的心肺訓練器材都有。而且這樣算下來，我一個月只花一千元，比去加州運動中心更划算。

感謝加州運動中心把我趕出來，讓我沒有花了錢變冤大頭，花了一大筆錢卻只用到他們最基本的跑步機等器材，(而且那個方案還不准週末使用)。感謝加州運動中心把同一性別赤身裸體集合起來脫衣洗澡，只考慮了男性與女性的需求，卻沒有考慮偽娘、扶他、跨性人的需求。感謝加州運動中心在性別隔離的觀念上相對落後，使我不用花太多冤枉錢，在我不需要的設備上。

台山話的兒歌

歌名：一姊不如二姊嬌

歌詞：
一姊不如二姊嬌
三寸金蓮四寸腰
買得五六七錢粉 (擦臉的化妝粉)
八九十支票 (鈔票的票)
十九月亮八分光 (農曆初十九的月亮沒有初十五的來得亮)
七更仙姊會六郎 (七夕牛郎織女)
五更四次扣三點 (表示時間過得很快)
兩人同睡一張床 (有情人終成眷屬)

當我用「一姊不如二姊嬌」用Google搜尋，竟然在國家文化資料庫，福佬話歌謠中發現。一模一樣的歌詞，但卻是用閩南語唱。所以我懷疑台山人一開始其實是福建來的，後來搬遷到廣東台山縣這一帶。