[UVA] 198 Peter's Calculator

題目：http://uva.onlinejudge.org/external/1/198.html

code & tests:
https://github.com/wilson100hong/UVAOJ/tree/master/Volume_1/198

想法：一行一行parse，根據三種不同的指令做如下動作
1. Assign
    含有 ":=" (assign operator) 的line都執行Assign。:=的左邊是variable name，右邊會是一個Expression。由於Expression內含recursive的桔構，我這裡使用tree來存儲Expression內的每一個Term，而每一個Term也是一個tree，包含著子Factor。由於題目的input皆是合法輸入，對於tree的每個children可以recursive parse。
    這個命令執行完時，我們會產生/取代一組variable name -> Expression的key value pair，也就是變數的定義。把定義存在global的map裡。

2. Reset
   去空白後，以RESET開頭的line皆執行Reset。把 variable name -> Expression map 清掉即可。

3. Print
    去空白後，以PRINT開頭的line皆印出變數evaluation出的數值。由於我們必需考慮undefined variable 和cyclic dependency的情況，我們必需先
  a. 確認當前變數被定義過
  b. 從當前變數往源頭變數們(":=" 右邊的變數們)迴溯，它們也必需被defined過。不斷迴溯，直到所有involved的變數為
   b1. 所依賴的變數皆定義過    或
   b2. 不依賴其它變數 (eg. a:=3)
   c. 如果符合，那麼所有會被evaluate到的變數都有被定義過了。第二步是check cyclic dependency，這一步用DFS即可。有cycle就是UNDEF

  排除undefined之後，就是evaluate變數。我這裡是用topological sort把所有involved變數的依賴性排序後，依ts order做evaluate。每次evaluate完一個變數後就存進cache裡來reuse。這樣的好處是evaluate一個變數時它依賴的變數們都有值了，可以值接從cache取出來，免除重複計算。


GY：
  這一題考的就是coding而已。不過還是有GY之處，而且都非常賤：
1. 空白行是合法的，跳過即可
2. token之間是可以沒有空白的。簡單起見，一開始就把空白trim掉
3. RESET 跟 PRINT 的前面也可以有空白 <-- waste me 4 hours