102-2 PDSA HW3

HW3-1. (30 points)

[題目] Write a stack client Parentheses that reads in a text file (file name is specified through standard input, args[0] ) and uses a stack to determine whether its parentheses are properly balanced.

先開一個新專案(HW3)，將作者提供的library加進來 (more)。

接著新增一個新的java source file (Parentheses.java)，題目已經明說要用stack來處理這個問題，可以直接使用作者提供的stacks (e.g. LinkedStack, ResizingArrayStack)，也就是說，這個作業直接寫main就好(把自己想成clients)。稍微比較一下LinkedStack.java與ResizingArrayStack.java的程式碼，兩個物件在宣告的時候都不用事先給stack size，也都接受generics (Generics: An essential characteristic of collection ADTs is that we should be able to use them for any type of data. more)。乍看之下，兩種implementation都不錯，優劣之處可參考作者的投影片p24)

就弄個String stack來用用吧! (也可以用Character stack試試)

接下來，從args[0]吃進檔名，開檔。檔案中應該只有一行，讀進來之後要切成一個個char。我是使用String物件中的toCharArray()，應該還有很多其他好方法。

實作過程中發現有幾個需要注意的地方：

1. 程式離開前要檢查一下stack是否清空? 會影響true/false
2. pop之前要檢查stack中是否有東西，避免產生exception

HW3-2. (55 points)

來到有名的Josephus problem。(可閱讀中文版比較有趣)

在這個作業中，要同時練習implementation (實作 circular queue)，也要練習當clients (寫main)。