【個人筆記】C++ ZeroJudge 基礎題庫解題(純練習) - part 2

a015.：https://zerojudge.tw/ShowProblem?problemid=a004

難度：★★★☆☆

二維陣列、巢狀迴圈應用。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int rows, cols;
    while (cin >> rows >> cols) {
        vector<vector<int>> matrix(rows, vector<int>(cols));
        
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                cin >> matrix[i][j];
            }
        }
        
        for (int j = 0; j < cols; ++j) {
            for (int i = 0; i < rows; ++i) {
                cout << matrix[i][j] << (i == rows - 1 ? "\n" : " ");
            }
        }
    }
    return 0;
}

vector 是個很好用的 data structure，可說是動態版的 array，在競程中也常使用到。

矩陣運算需要使用到二維的結構，所以於此便定義一個二維的 vector 結構出來。

一維 vector 定義：vector <int> my_vector
二維 vector 定義：vector<vector<int>> my_vector

vector<vector<int>> matrix(rows, vector<int>(cols)); 這行等效於如下：

int matrix[rows][cols] = 
{
{0,0,0,.......},
{0,0,0,.......},
{0,0,0,.......},
{0,0,0,.......},
.......
}

表示建立一個 rows 列、cols 行的矩陣。

題目敘述當中有提示：* 測資檔會包含多組矩陣資料，所以要注意加上 while (cin >> rows >> cols) 的寫法。

for (int j = 0; j < cols; ++j) {
    for (int i = 0; i < rows; ++i) {
        cout << matrix[i][j] << (i == rows - 1 ? "\n" : " ");
    }
}

也可以從題目範例測資看到，輸出結果是務必要將 rows、cols 反過來，矩陣裡面的一串數字也要顛倒過來。

而在沒有使用 vector 的情況下，使用陣列需要設定一個固定值（看題目要求 rows、cols 大小去固定大小），於講求執行效率跟記憶體空間使用的「競程」來說，vector 顯然是最佳解（動態記憶體跟動態大小）。

而用到三元運算子是為了符合題目的輸出格式所用。

---

a017.：https://zerojudge.tw/ShowProblem?problemid=a017

難度：★★★★★

運算子優先級、演算法、資料結構、字串處理

#include <iostream>
#include <sstream>
#include <stack>
#include <vector>
#include <unordered_map>

using namespace std;

// 運算子優先級表
unordered_map<char, int> precedence = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'%', 2}};

// 檢查是否為運算子
bool isOperator(char c) {
    return precedence.find(c) != precedence.end();
    // std::find() 尋找 key 有無在雜湊表內
    // 有 -> 回傳 iterator, 無 -> 回傳 precedence.end()
}

// 中序轉後序（RPN：Reverse Polish Notation）、Shunting-yard 演算法
vector<string> infixToPostfix(const vector<string>& tokens) {
    vector<string> output; // 建立 output vector 容器
    stack<char> operators; // 建立 operators 堆疊容器
    
    for (const string& token : tokens) { // range-based for loop
        if (isdigit(token[0])) { // 數字直接輸出
            output.push_back(token); // push_back(), 在尾端插入元素(vector用)
        } else if (token == "(") { // 左括號入 stack
            operators.push('(');
        } else if (token == ")") { // 右括號則彈出直到左括號
            while (!operators.empty() && operators.top() != '(') {
                output.push_back(string(1, operators.top()));
                operators.pop();
            }
            operators.pop(); // 移除左括號
        } else if (isOperator(token[0])) { // 運算子
            while (!operators.empty() && isOperator(operators.top()) &&
                   precedence[operators.top()] >= precedence[token[0]]) {
                output.push_back(string(1, operators.top()));
                operators.pop();
            }
            operators.push(token[0]);
        }
    }
    
    while (!operators.empty()) { // 剩餘運算子移出 stack
        output.push_back(string(1, operators.top()));
        operators.pop();
    }
    
    return output;
}

// 計算後序表示法的值
int evaluatePostfix(const vector<string>& tokens) {
    stack<int> values;
    
    for (const string& token : tokens) {
        if (isdigit(token[0])) {
            values.push(stoi(token));
        } else {
            int b = values.top(); values.pop();
            int a = values.top(); values.pop();
            
            if (token == "+") values.push(a + b);
            else if (token == "-") values.push(a - b);
            else if (token == "*") values.push(a * b);
            else if (token == "/") values.push(a / b);
            else if (token == "%") values.push(a % b);
        }
    }
    
    return values.top();
}

int main() {
    string line;
    while (getline(cin, line)) {
        stringstream ss(line);
        string token;
        vector<string> tokens;
        
        while (ss >> token) {
            tokens.push_back(token);
        }
        
        vector<string> postfix = infixToPostfix(tokens);
        int result = evaluatePostfix(postfix);
        cout << result << endl;
    }
    
    return 0;
}

此題用到了所謂的「（後綴、後序）逆波蘭表示法（Reverse Polish Notation, RPN）」、「排程場演算法（Shunting-yard）」。

至於函式庫，則為：

1. 「#include <sstream>」：字串流
2. 「#include <stack>」：堆疊，用於運算子優先順序與後序計算
3. 「#include <unordered_map>」：雜湊表，用於運算子優先順序查找

:::success
逆波蘭表示法（Reverse Polish Notation, RPN）：所有運算子置於運算元的後面。

例如：a+b 變成 ab+。

a+b 稱為中序，使用此表示法將其轉為後序 ab+。

以下是 RPN 在程式設計上的做法（即使用到排程場演算法（Shunting-yard））：

1. 由左至右讀取運算式中的字元
2. 若為運算元, 則複製到後序運算式字串中
3. 若為左括號, 則 push 至 stack 中
4. 若為右括號, 從 stack 中 pop 字元至後綴表達式, 直到遇到左括號, 然後把左括號 pop 出來
5. 若為運算子, 且若此時 stack top 的運算子優先級 ≥ 此運算子, 彈出 stack top 的運算子到後綴表達式, 直到發現優先級更低的元素位置, 把運算子 push 至 stack
6. 讀到輸入的尾端, 將 stack 元素 pop 出來直到該 stack 為 empty, 將符號寫入後序運算式中

參照：https://clu.gitbook.io/data-structure-note/stack-reverse-polish-notation

排程場演算法是專門用於將中序轉後序的演算法。
:::

---

#include <unordered_map> 是一種針對雜湊表的 key-value 容器。（STL 標準函式庫）

與 std::map 不同，unordered_map 不保證元素的排序，但通常提供更快的查找速度（時間複雜度O(1)）。

map：有序；unordered_map：無序（其實從英文上就看得出來了：unordered）。

以下是基礎語法：

#include <unordered_map>

std::unordered_map<key_type, value_type> map_name;

key_type：鍵的資料型態。

value_type：值的資料型態。

map_name：自定義名稱。

要初始化一個 unordered_map，如下：

std::unordered_map<std::string, int> umap = {
    {"Tom", 1},
    {"Ann", 4},
    {"Jack", 2}
};

插入元素：

myMap.insert({3, "three"});

or

myMap[1] = "one"; // 會直接覆蓋 key = 1 的值

存取元素：

std::string value = myMap[1]; // 獲取鍵為 1 的值

刪除元素：

umap.erase(umap.begin()); // 刪除開頭的元素

myMap.erase(1); // 刪除鍵為 1 的元素

umap.erase(umap.find("John"), umap.end()); // 刪除從某元素開始至尾端的元素

搜尋元素：

auto it = myMap.find(2); // 尋找鍵為 2 的元素
if (it != myMap.end()) {
    std::cout << "Found: " << it->second << std::endl;
}

---

<sstream> 允許你將字串當作 “輸入 / 輸出流” 來使用，這使得從字串中讀取資料或將資料寫入字串變得非常簡單。

sstream 是 C++ STL 中其中一個的命名空間，包含幾個 class，如下：

• istringstream：用於從字串中讀取資料。
• ostringstream：用於將資料寫入字串。
• stringstream：是 istringstream 和 ostringstream 的組合，可以同時進行讀取和寫入運算。

基本語法：

#include <sstream>

// 使用 istringstream
std::istringstream iss("some data");

// 使用 ostringstream
std::ostringstream oss;

// 使用 stringstream
std::stringstream ss;

具體應用大致如下：

1. 從字串讀取資料：如從字串中讀取整數、浮點數等。（iss >> num1 >> num2）
2. 向字串寫入資料
3. 使用 stringstream 進行讀寫運算

:::success
反正就是把：

1. istringstream 看成輸入流 “>>”
2. ostringstream 看成輸出流 “<<”
   :::

但是通常用 std::stringstream ss; 因為他兩者具備。

具體範例可至：https://hackmd.io/@Maxlight/rJwlvj8ad

---

接下來是最後一個函式庫 <stack>：

同樣也是 C++ STL 的一部分，也實現了後進先出（LIFO，Last In First Out）的資料結構，對嘛，堆疊的性質就是如此。

以下是 stack 的基本運算：

• push(): 在堆疊頂端增加一个元素。
• pop(): 移除堆疊頂端的元素。
• top(): 回傳堆疊頂端元素的參考，但不移除它。
• empty(): 檢查堆疊是否為空。
• size(): 回傳堆疊中元素的數量。

要建立一個堆疊：

std::stack<int> s;

---

參考資料

C++ 容器类| 菜鸟教程

C++ std::unordered_map 用法與範例 | ShengYu Talk

C++ std::stack 用法與範例 | ShengYu Talk

C++ 容器类| 菜鸟教程