題目連結:
題目大意:
有三個函數:
f(x) = 2x - 3
g(x, y) = 2x + y - 7
h(x, y, z) = 3x - 2y + z
而我們可以將函數的輸出也作為另一個函數的參數,如 h(f(5), g(3, 4), 3) = h(7, 3, 3) = 18 。
而上述這種表示法 h(f(5), g(3, 4), 3) 可以簡化為 h f 5 g 3 4 3 (也就是刪除所有括號以及逗號並以空白隔開剩下的東西)。
現在輸入給定你一個如上的簡化式(少於 1000 個字元,且參數值為 -1000 ~ 1000 的整數),求輸出為何?保證可以計算(保證過程中出現的數字介於 -10 ^ 9 ~ 10 ^ 9 之內)。
範例輸入:
範例輸入 #1
f f f 2
範例輸入 #2
h f 5 g 3 4 3
範例輸出:
範例輸出 #1
-5
範例輸出 #2
18
解題思維:
順著看比較不好做,而反著看就比較好做了,此時我們可以利用堆疊(Stack)暫存參數。
例如範例輸入 #2 的 h f 5 g 3 4 3 ,反著看是 3 4 3 g 5 f h (如果是用字串存整串輸入的話,記得數字也會被倒過來喔)
3 4 3 g 5 f h
現在遇到的是數字 3 ,所以推入堆疊內(從左到右為堆疊的底端到頂端)。
堆疊:3
3 4 3 g 5 f h
現在遇到的是數字 4 ,所以推入堆疊內。
堆疊:3 、 4
3 4 3 g 5 f h
現在遇到的是數字 3 ,所以推入堆疊內。
堆疊:3 、 4 、 3
3 4 3 g 5 f h
現在遇到了 g ,所以將從堆疊頂端移出兩個元素作為參數。因為越靠近頂端的是越前面的參數,所以得到 x = 3 、 y = 4 ,因此得到 g(x, y) = 3 ,然後將該值放入堆疊。
堆疊:3 、 3
3 4 3 g 5 f h
現在遇到的是數字 5 ,所以推入堆疊內。
堆疊:3 、 3 、 5
3 4 3 g 5 f h
現在遇到了 f ,所以從堆疊移出一個元素作為參數,得到 x = 5 ,而 f(5) = 7,所以將 7 推入堆疊。
堆疊:3 、 3 、 7
3 4 3 g 5 f h
現在遇到了 h ,所以所以從堆疊移出三個元素作為參數,得到 x = 7 、 y = 3 、 z = 3,而 h(7, 3, 3) = 18,所以將 18 推到堆疊裡。
堆疊:18
最後堆疊剩下的那唯一一個數字(如此例的 18)即是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。