推 sasbluesea:第五題 按照編號 往下DFS並標上標號 遇到同編號即有環 01/01 05:58
推 louis719:第一題(b)我覺得應該是要插在while()迴圈後面 01/01 18:01
→ louis719:precede我寫的和你一樣 我覺得答案怪怪的 01/01 18:02
→ louis719:他多加的那段code是在處理遇到')'時要把'('pop出去的case 01/01 18:04
http://ezproxy.lib.ncu.edu.tw:8080/~arhui/cexamn/exam/EC02_96_01.pdf
第一題
我手邊的答案是寫
(a)
7 topsymb=(pop(stk);
8 add topsymb to the postfix string;}
9 push(stk, symb);}
11 topsymb=(pop(stk);
12 add topsymb to the postfix string;}
(b)
line 10, line 11 is replaced by the statement x
precede('(', op) returns TRUE.
precede(op, ')') returns FALSE.
a的部分我跟他一樣
b的部分我就有點不懂...
為什麼是把第10行跟11行換成x這邊的敘述
第10行那邊是在把stack裡的東西清空不是嗎?
我是不太曉得這四行要加在哪,原本那樣不就可以了...
如果要加在第六行while迴圈之前
會變成沒判別符號優先權,只要不是')'就直接push進去(X)
如果加在第十行while迴圈前,那之前就已經處理完了
不是變得很累贅= =?
還有後面那兩個敘述跟我寫的相反= ="
照他那樣寫,會變成輸入')'的時候,會直接把')'push進去吧?
另外,第五題有人有想法嗎?
我原本的想法
1.先判斷m是否等於n-1
2.建立n個node
3.從text file的第二行開始,進行union by height判斷有無cycle
4.檢查是否n個node皆為同一個group(連通),若是則為tree
不過step3,會花O(mlogn)=O(nlogn)
不符合題目的O(n)
懇請幫忙囉
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.27.237.182
※ 編輯: genius945 來自: 114.27.237.182 (01/01 01:40)