---
tags: sprout
---

# 第 12 周作業講解

## 排隊停車

### 解題思路
- 只要分別把三種操作完成就好了
- 需要支援頭尾的插入、移除，所以採用 deque 來實作
- 每個車子都要記錄車牌、價錢，也許可以用 pair 來簡化

### 程式框架
我們需要先讀入兩個整數 `space` 跟 `cmd_cnt` 代表一開始的車位數與指令數，並讀入指定數量的指令並進行操作，最後輸出。

那這裡就利用前面提到的 deque 跟 pair 來幫助我們完成這一題

#include <bits/stdc++.h>

using namespace std;
typedef pair<string, int> Car;

int main() {
    int space = 0, cmd_cnt = 0;
    cin >> space >> cmd_cnt;

    deque<Car> line;
    while (cmd_cnt--) {
        string command;
        cin >> command;
        if (command == "Car") {
            // do something
        }
        else if (command == "Leave") {
            // do something
        }
        else if (command == "Price") {
            // do something
        }
    }
    
    // output
}

### 操作一（Car）

當有一輛車進來的時候，我們要考慮幾種狀況：
1. 有車位：那就停進去，此時車位會減少一個
2. 沒車位，但願意排隊：那就放到 deque 的最後面
3. 沒車位也不願意排隊：那就甚麼事都不用做

所以我們需要紀錄的事情有：
- 車位的數量：使用輸入的 `space` 來紀錄即可
- 隊伍的長度：deque 有支援 `size()` 方法，可以直接使用

寫起來大概會像這樣：

if (command == "Car") {
    string id;
    int max_len = 0;
    int max_price = 0;

    cin >> id >> max_len >> max_price;

    if (space > 0) {
        space--;
    }
    else if (line.size() < max_len) {
        line.push_back(make_pair(id, max_price));
    }
    else {
        // do nothing
    }
}

### 操作二（Leave）
有一輛車離開，一樣也是要來討論幾種狀況：
- 有車在排隊：讓隊伍裡的第一輛車進去，車位數不變
- 沒車在排隊：直接離開，車位數加一

要額外紀錄的資訊與操作一相同。
寫起來大概會像：

else if (command == "Leave") {
    if (line.empty()) {
        space++;
    }
    else {
        line.pop_front();
    }
}

### 操作三（Price）
這裡就不需要討論甚麼情況了，一直把最後面符合條件的車子移除即可。

那這裡會需要用到每個車子的期望價錢，這個資訊可以從我們存進 line 的 pair 裡的 second 來取得。

寫起來像是：

else if (command == "Price") {
    int price = 0;
    cin >> price;
    while (!line.empty() and line.back().second >= price) {
        line.pop_back();
    }
}

### 輸出格式
就判斷一下隊伍裡還有沒有東西來決定要輸出甚麼，千萬記得行末不空格

if (line.empty()) {
    cout << "empty";
}
else {
    cout << line.front().first;
    line.pop_front();
}

while (!line.empty()) {
    cout << " " << line.front().first;
    line.pop_front();
}

cout << "\n";

### 完整程式碼

#include <bits/stdc++.h>

using namespace std;
typedef pair<string, int> Car;

int main() {
    int space = 0, cmd_cnt = 0;
    cin >> space >> cmd_cnt;

    deque<Car> line;
    while (cmd_cnt--) {
        string command;
        cin >> command;
        if (command == "Car") {
            string id;
            int max_len = 0;
            int max_price = 0;

            cin >> id >> max_len >> max_price;

            if (space > 0) {
                space--;
            }
            else if (line.size() < max_len) {
                line.push_back(make_pair(id, max_price));
            }
        }
        else if (command == "Leave") {
            if (line.empty()) {
                space++;
            }
            else {
                line.pop_front();
            }
        }
        else if (command == "Price") {
            int price = 0;
            cin >> price;
            while (!line.empty() and line.back().second >= price) {
                line.pop_back();
            }
        }
    }

    if (line.empty()) {
        cout << "empty";
    }
    else {
        cout << line.front().first;
        line.pop_front();
    }

    while (!line.empty()) {
        cout << " " << line.front().first;
        line.pop_front();
    }

    cout << "\n";
}

******

## 整數四則運算機

### 解題思路

把題序念過一次，然後照著上面的方式寫，~~我很想把題序直接複製貼上到這裡~~

這題最需要注意的點就是優先權與括號的處理：
- 優先權方面：每次放入運算符時，都要把運算符 stack 裡優先權大於等於自己的通通都先計算完畢
- 括弧：所有的計算遇到左括弧就必須停止，要放入右括弧時會無條件進行計算，直到遇到一個左括弧為止

細節後面再逐一介紹

### 框架
這邊我們來跟著題序一步一步的做：
> 聽起來很複雜，其實可以用這周上課學到的資料結構 stack 來實作，我們需要兩個堆疊，一個放運算子，一個放數字

宣告兩個 stack，沒什麼好說的

#include<bits/stdc++.h>

using namespace std;

stack<char> op_stack;
stack<int> num_stack;

int main() {}

<br/>

>由左到右讀取算式，是數字就 push 到數字的堆疊上，是運算子就放到運算子的堆疊上

讀輸入，並判斷是數字還是算符，這裡特別注意負數的檢查哦。
然後下面用到的 `isdigit` 函式是用來檢驗給定的字元是不是數字，類似用法的還有 `isalpha`、`isupper`、`islower`

int main() {
    string input;

    while (cin >> input) {
        if (input.size() > 1 or isdigit(input[0])) {
            num_stack.push(stoi(input));
        }
        else {
            op_stack.push(input[0]);
        }
    }
}

<br/>

> 因為在運算子堆疊頂部的運算子優先權比較大，要先計算
> 因為要由左到右計算，所以也要先計算堆疊上的運算子
> 運算子堆疊空了，所以就直接把減法放入

這裡的 `get_weight` 是用來取出運算子的優先權的，之後再把它完成即可
`calculate` 是負責處理運算、丟棄用過的運算子用的，也是後面再完成

if (input.size() > 1 or isdigit(input[0])) {
    num_stack.push(stoi(input));
}
else {
    while (!op_stack.empty() and get_weight(input[0]) <= get_weight(op_stack.top())) {
        calculate();
    }
    op_stack.push(input[0]);
}

<br/>

> 那括號的處理也類似，簡單來說，遇到左括號就直接放入堆疊，遇到右括號就一直取出堆疊上的運算子來執行直到堆疊頂是左括號為止。

直接把兩個括號抓出來分開討論就好了

while (cin >> input) {
    if (input.size() > 1 or isdigit(input[0])) {
        num_stack.push(stoi(input));
    }
    else if (input == "(") {

    }
    else if (input == ")") {

    }
    else {
        while (!op_stack.empty() and get_weight(input[0]) <= get_weight(op_stack.top())) {
            calculate();
        }
        op_stack.push(input[0]);
    }
}

<br/>

>沒有輸入後就依序把運算子堆疊的運算子拿出來，根據運算子操作數字堆疊上的數字，最後數字堆疊會剰一個數字，那就是我們要的答案

不要忘記輸出餒

int main() {
    /*
    剛剛的東西
    */

    while (!op_stack.empty()) {
        calculate();
    }

    cout << num_stack.top() << endl;
}

### get_weight

這個部分還滿自由的，看是喜歡很多 if-else 還是用陣列去做搜尋、指定都可以，這裡就用簡單的 if-else 示範：

int get_weight(char op) {
    if (op == '+') {
        return 0;
    }
    if (op == '-') {
        return 0;
    }
    if (op == '*') {
        return 1;
    }
    if (op == '/') {
        return 1;
    }
}

### calculate
藉由判斷 `op_stack` 頂層的符號是甚麼來決定要做甚麼運算，特別注意從 `num_stack` 抓東西出來的順序是從算式的右邊到左邊的，沒處理好的話減法跟除法就會出錯

void calculate() {
    char op = op_stack.top();
    op_stack.pop();

    int a = num_stack.top();
    num_stack.pop();
    int b = num_stack.top();
    num_stack.pop();
    int ans = 0;

    if (op == '+') {
        ans = b + a;
    }
    if (op == '-') {
        ans = b - a;
    }
    if (op == '*') {
        ans = b * a;
    }
    if (op == '/') {
        ans = b / a;
    }

    num_stack.push(ans);
}

<br/>

### 括弧處理

左括號：看到直接放入，如果計算的時候遇到他就必須中止
顯然的，我們目前遇到左括號並不會終止，我們有兩種做法來解決這個問題：
1. 再加入運算符時的那個迴圈加入更多的限制條件，讓他在遇到左括號時不會繼續呼叫 `calculate`
2. 也許可以給左括號更小的優先權？

第二種雖然可以省一點 code，但比較迂迴，這裡使用直觀易懂的第一種作法

至於右括號，就是一直把 `op_stack` 裡的運算符拿出來計算，直到遇到左括號時停下，並一起把左括號帶走，完成後如下：

while (cin >> input) {
    if (input.size() > 1 or isdigit(input[0])) {
        num_stack.push(stoi(input));
    }
    else if (input == "(") {
        op_stack.push('(');
    }
    else if (input == ")") {
        while (op_stack.top() != '(') {
            calculate();
        }
        op_stack.pop();
    }
    else {
        while (!op_stack.empty() and op_stack.top() != '(' and get_weight(input[0]) <= get_weight(op_stack.top())) {
            calculate();
        }
        op_stack.push(input[0]);
    }
}

<br/>

### 完整程式碼

不要理會那個 `return 4328;` 單純是因為看到 warning 所以不開心w

#include<bits/stdc++.h>

using namespace std;

int get_weight(char);
void calculate();

stack<char> op_stack;
stack<int> num_stack;

int main() {
    string input;

    while (cin >> input) {
        if (input.size() > 1 or isdigit(input[0])) {
            num_stack.push(stoi(input));
        }
        else if (input == "(") {
            op_stack.push('(');
        }
        else if (input == ")") {
            while (op_stack.top() != '(') {
                calculate();
            }
            op_stack.pop();
        }
        else {
            while (!op_stack.empty() and op_stack.top() != '(' and get_weight(input[0]) <= get_weight(op_stack.top())) {
                calculate();
            }
            op_stack.push(input[0]);
        }
    }

    while (!op_stack.empty()) {
        calculate();
    }

    cout << num_stack.top() << endl;
}


int get_weight(char op) {
    if (op == '+') {
        return 0;
    }
    if (op == '-') {
        return 0;
    }
    if (op == '*') {
        return 1;
    }
    if (op == '/') {
        return 1;
    }
    return 4328;
}

void calculate() {
    char op = op_stack.top();
    op_stack.pop();

    int a = num_stack.top();
    num_stack.pop();
    int b = num_stack.top();
    num_stack.pop();
    int ans = 0;

    if (op == '+') {
        ans = b + a;
    }
    if (op == '-') {
        ans = b - a;
    }
    if (op == '*') {
        ans = b * a;
    }
    if (op == '/') {
        ans = b / a;
    }

    num_stack.push(ans);
}

### 後記

正當我覺得的我把這份 code 寫得很冗的時候，我發現我前幾天試寫的 code 更醜QQ
然後其實這一題也可以用遞迴來處理掉左右括號的問題，各位可以再次把這題當成隨堂練習哦！

## 介紹一些寫 code 的小撇步？

### 編譯

因為下面很多東西都會用到 terminal（用你們的 IDE 可能也可以，但我很少用所以不知道），所以這裡簡單介紹一下如何使用 terminal 來編譯你的程式
For Windos command prompt：
1. 打開你放程式的目錄，右鍵並選擇 `Open in Terminal`（當然你也可以打開 Terminal 後再 `cd` 過去），總之就是打開 Terminal，並把工作目錄移動到你放 cpp 檔的位置
2. 然後輸入指令 `g++ filename.cpp -o output`，`filename.cpp` 請改成你的程式的檔名，`-o output` 可以用來指定你編譯出來的執行檔的檔名，如果不加的話就會使用預設的檔名
3. 然後輸入指令 `output`（`output` 是剛剛編譯出來的執行檔檔名）就可以執行了

For Max and Linux（~~企鵝真香~~）：
應該也差不多，只是可能沒有 `Open in Terminal` 這個選項可以用，要自己學一下 `cd` 的用法。

### 測試

如果覺得每次測試都要手動複製貼上測資很麻煩，看這裡就對了！
1. 把測資存成一個純文字檔，並把他跟編譯好執行檔放在同一個資料夾
2. 下指令 `exename < testdata`，`exename` 是執行檔的名字，`testdata` 是放測資的檔名
3. 然後就會輸出結果了，需要的話也可以用 `exename < testdata > name` 把輸出放在 `name` 這個檔案裡面

### Print 大法

如果找不到蟲也不知道從哪裡開始抓蟲，就先把所有東西都印出來吧！
在印的時候要特別注意有沒有以下的問題：
1. 印出來的變數跟你想像的是不是一樣的
2. 各個操作是不是都有正確執行
3. 程式如果 crash 了，那是哪一段程式碼造成的

相信其實這個技巧大家已經很熟練了，只是在上傳時偶爾會忘記把 `cout` 註解掉...

所以介紹一個我比較常用的方法：用 `#ifdef DEBUG` 跟 `#endif` 來把測試用的 `cout` 包起來，就像這樣：

#include<iostream>

int main() {
    #ifdef DEBUG
    std::cout << "start success!" << endl;
    #endif
}

`DEBUG` 可以換成其他你喜歡的名字，而我們只要在編譯的時候把指令加上 `-D{name}` （例如這裡就是 `g++ filename.cpp -o output -DDEBUG`），編譯出來的執行檔就會包含 `#ifdef` 裡的內容了，如果不加則會無視，所以寫完測試完後就可以直接上傳，不用再慢慢註解了

### assert

有時候你寫的程式會少考慮一些情況或是做出一些奇怪的事情，最後導致 WA，而這種蟲個人覺得還滿難抓的，這時候就可以利用 assert 來幫忙尋找這些蟲。

用法：
- 用 cassert 函式庫
- `assert(condition);` 當 `condition` 為 `false` 時就會報錯，反之甚麼事都不會發生

例子：

int get_weight(char op) {
    if (op == '+') {
        return 0;
    }
    if (op == '-') {
        return 0;
    }
    if (op == '*') {
        return 1;
    }
    if (op == '/') {
        return 1;
    }
    assert(0);
    return 4328;
}

（參考整數四則運算機說明）按照我們的想法，這個函式一定不會執行到 `return 4328`，如果執行到那裡就代表程式一定有問題，而且這個回傳值基本上還不太會讓我們的程式 crash，我們只會一直吃 wa 但不知道 wa 在哪，所以我們就可以加上 `assert(0)`，讓他如果意外的執行到那裡時可以報錯，把 wa 變成 re

### 風格
把程式寫好看一點，這樣別人跟講師在幫你抓蟲的速度跟完整度都會更好喔！（而且搞不好自己看一看就看出來了）