術語介紹:若有一算式a+b,則a 跟b 是運算元,+是運算子
我們將算式從中序轉後序之後,就可以利用stack 把答案算出來!計算的方法是
1. 如果是運算元,那就直接Push 到stack 中
2. 如果是運算子,那就Pop 出stack 最上面兩個數字,算完再Push 回去
舉個例子:假如後序是 1 2 + 4 –
那我們會先把1,2 丟進stack;然後碰到“+”時把1,2 拿出來計算,再把答案3 丟
回stack;然後把4 丟到stack,碰到”-“時再把stack 的3,4 拿出來處理,再把答
案-1 丟回stack;算式結束後,stack 中剩下的值(唯一存在的)就會是答案。
第⼀個數字N,表示N 組測資。
接下來N 行,每行表示⼀組測資。
每行有⼀個開頭數字M,代表運算元加運算子總共有多少符號。
然後,後面接著有M 個符號,且任兩個運算元或運算子中間會以空白隔開。
每行運算元以及運算子加起來最多1000 個。
每個運算元為絕對值小於等於1000 的整數,運算子有”+”,”-“
對於每組測資,輸出該算式的答案。