今天的題單：

• Evaluate Reverse Polish Notation

• Course Schedule

150. Evaluate Reverse Polish Notation

思路: 觀察計算的模式，可以利用 stack 來保持正確的計算順序。依照順序讀取 token，當遇到數字就放入 stack，遇到計算符號就把 stack 內的上面兩個數字拿出來計算，把結果 push 進 stack。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;
        
        vector<string>::iterator it = tokens.begin();

        while (it != tokens.end()) {
            int a, b;
            if (*it == "+") {
                b = stk.top();
                stk.pop();
                a = stk.top();
                stk.pop();
                stk.push(a + b);
            } else if (*it == "-") {
                b = stk.top();
                stk.pop();
                a = stk.top();
                stk.pop();
                stk.push(a - b);
            } else if (*it == "*") {
                b = stk.top();
                stk.pop();
                a = stk.top();
                stk.pop();
                stk.push(a * b);
            } else if (*it == "/") {
                b = stk.top();
                stk.pop();
                a = stk.top();
                stk.pop();
                stk.push(a / b);
            } else {
                stk.push(stoi(*it));
            }
            it++;
        }

        return stk.top();
    }
};

207. Course Schedule

思路: 把課程當 node，prerequisites當 edge，可以建一個 graph。如果能成功修完所有課，這個 graph 必須沒有環。如果有環，這個環內的課都沒辦法修，道理與 deadlock 相同。因此，這個問題可以轉換成判斷一個有向圖 (Directed Graph) 內有沒有環的問題。

Attempt 1: DFS

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);  // adjcent list
        vector<bool> visited(numCourses, false);
        vector<bool> rec_stack(numCourses, false);

        for (auto& edge : prerequisites) {
            graph[edge[0]].push_back(edge[1]);
        }

        bool has_cycle = false;
        
        // check if there is a cycle in the graph
        for (int i = 0; i < numCourses; i++) {
            if (check_cycle(i, visited, rec_stack, graph)) {
                has_cycle = true;
                break;
            }
        }

        return !has_cycle;
    }

    bool check_cycle(int node, vector<bool>& visited, vector<bool>& rec_stack, vector<vector<int>>& graph) {
        visited[node] = true;
        rec_stack[node] = true;
        
        for (auto& neighbor : graph[node]) {
            if (!visited[neighbor] && check_cycle(neighbor, visited, rec_stack, graph)) {
                return true;
            } else if (rec_stack[neighbor]) {
                return true;
            }
        }

        rec_stack[node] = false;

        return false;

    }
};