# Ch5. 字串 解題指引
## 先備知識

### 字元

`char`是C/C++的基本資料型態，大小為一個位元組 (1 byte)，可以儲存單一個字元。

例如，宣告一個字元型態變數`ch`，值為字母 A，寫法如下：

char ch = 'A';  // 將字元 A 設定給字元變數 ch。

C++使用一對**單引號`''`**，將一個字元括起來，代表他的 ASCII 碼。

我們可以宣告字元變數，搭配使用`cin`，嘗試從鍵盤讀入一個字元：

char c;
cin >> c;
cout << c;

注意`cin`會跳過換行、空白、tab等空字元，只讀取一個字母。因此，若輸入為：`a b` ，以上程式將只會輸出字母 a 。

### ASCII code

ASCII code 全名為「American Standard Code for Information Interchange」，是一套依據拉丁字母的電腦編碼系統。在電腦中，所有的資料在儲存和運算時都要使用二進位數表示。而具體用哪些二進位數字表示哪個符號，這就是編碼。如果不同的電腦要想互相通信而不造成混亂，那麼每台電腦就必須使用相同的編碼規則，於是美國有關的標準化組織就推出了ASCII編碼。

字元最大的用處，就是以 ASCII 碼的形式，將文字資訊顯示出來。基本 ASCII code 對照表如下。數字 0~127 ，分別對應到大、小寫英文字母、阿拉伯數字、一些半形標點符號，還有一些控制字元。


我們可以將ASCII碼，設定給字元變數。例如，將字元 A 設定給字元變數 ch，以下寫法有相同的效果：

char ch = 65;  // 將 ASCII 碼為 65 的字元設定給字元變數 ch。

程式將 ASCII 碼指定給`char`型態的變數，因此若接續以`cout`輸出，會顯示字母 A，而非整數 65。

cout << ch;  // A

### 字串

當我們想要表達的文字超過一個字母時，就必須使用 **「字串」**。在C++語言中，有兩種儲存字串的方式，均須使用雙引號`""`將所需字串括起來:

**1) 以字元陣列（`char array`）來宣告字串：**

char s2[ ] = "HAPPY" ;

在上面這個例子，記憶體會使用連續的 6 個位元組來記錄字串`"HAPPY"`，參考課本3-5。最後一個字元為 `'\0'`，代表字串的結束。這種用法同時適用於C語言，但使用方法比較繁瑣，課堂上就不說明了，有興趣的孩子可以閱讀課本相關章節，或是參考[這篇教學文章](https://www.csie.ntu.edu.tw/~b98902112/cpp_and_algo/cpp02/string.html)。

**2) 以`string`類別宣告字串：**

string s1 = "abcd";

`string` 是一個保存 `char` 的類別物件，是一個**長度可變動**之字元序列，減輕了 C 語言風格字串的麻煩。如需使用`string` ，必須引入標頭檔`string` 。

現在，我們來寫一個程式，使用者輸入什麼字，程式就吐出什麼字：

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;    // 宣告字串s
    cin >> s;    // 輸入字串s
    cout << s << endl;    // 輸出字串s
    return 0;
}

| 範例輸入 | 範例輸出 |
| --- | --- |
| `Hello` | `Hello` |

從以上程式可以發現，在`main`函式之前要加上一行`#include <string>`，引入標頭檔`string`，否則編譯可能會發生錯誤。

請注意，如果讀取字串遇到空白，換行等空字元就會斷開，無法讀取整行。我們可以使用以下程式，將單字一個、一個讀取，作出相應行為，例如一個一個輸出：

string s;    // 宣告字串s
while(cin >> s)    // 只要有下一個輸入字串s
    cout << s << endl;    // 就輸出字串s

| 範例輸入 | 範例輸出 |
| --- | --- |
| `Tony Stark` | `Tony`<br/>`Stark` |

然而在某些狀況下，我們會需要一次讀取一整行輸入，此時就必須搭配使用`getline()`函式，請參考課本 3-5 的說明。

## 秘密差

### 解題步驟

- 以字串型態讀取輸入數字。
- 使用迴圈遍歷字串中每一個字元，根據索引值判斷奇/偶位數。
- 字元轉整數，奇/偶位數分別加總後求出秘密差。

### 引導問題（點擊箭頭展開提示）

::: spoiler **Q. 如何輸入字串，然後依序檢查字串中的每個字元？**
A. 建議使用`string`。接著請在課本中尋找，用什麼函式能取出**字串長度**，作為`for`迴圈的終止條件？在迴圈之中，又如何表示字串內的每個字元？
:::

::: spoiler **Q. 如何將每個位數的數字，從`char`轉成`int`型態？**
A. 以下舉例說明，如何將數字 123 的每個位數依序顯示出來，中間以空白間隔。

【錯誤方法】

string s = "123";
for(int i = 0; i < 3; i++)
    cout << (int)s[i] << " ";
// 輸出結果：49 50 51

以上程式直接使用`int`進行型別轉換，然而轉換後的結果依序為數字 1, 2, 3 的ASCII碼，並非其真正的數值。

* ==【法一】扣掉 0 的 ASCII code==

已知數字 0 的 ASCII code 為 48 ，那麼將每個數字字元轉換成 ASCII 碼之後，每個都扣掉 48，就是原始數值了。

string s = "123";
for(int i = 0; i < 3; i++)
    cout << (int)s[i] - 48 << " ";
// 輸出結果：1 2 3

* ==【法二】直接扣掉 '0'==

如果忘記數字 0 的 ASCII 碼，那有什麼關係！我們其實可以把兩個字元直接做加減，計算他們的「距離」。

上面的程式碼微調如下，計算字元`s[i]`與字元`0` 的 ASCII 碼相差多少，同樣能夠依序顯示 1, 2, 3。

string s = "123";
for(int i = 0; i < 3; i++)
    cout << s[i] - '0' << " ";
// 輸出結果：1 2 3

:::

::: spoiler **Q. 如何使用 `for` 迴圈，將每一回合得到的數字加起來？**

A. 宣告總和變數，累加計算結果，上禮拜應該有稍微複習到。以下舉例說明，如何計算數字 1 ~ 10 的總和。

int sum = 0;
for(int i = 1; i <= 10; i++)
    sum += i;
cout << sum;  // 輸出 55

因為本題要分別計算奇位數字和和偶位數字和，會需要兩個總和變數。因此，你需要在`for`迴圈中，判斷該位數是奇位數字還是偶位數字，累加到相應的總和變數。
:::

::: spoiler **Q. 如何判斷是奇數位數字，還是偶數位數字？**

取決於使用`for`迴圈檢查字元的順序。如果你從字串第 0 位，也就是最高位開始檢查，它可能是奇位數字或偶位數字，需要用**字串長度**判斷是哪一種。如果你從字串最後一位開始檢查(小心迴圈起始條件)，那它一定會是奇位數字。程式架構如下：

for(int i...){
    if(...) // 奇位數字
    {...} // 加總奇位數字和
    else  // 偶位數字
    {...} // 加總偶位數字和
}

:::

## **a108: 計算字串間隔距離**

### 解題步驟

- 依序輸入一個字串，與一個目標字母。
- 檢查字串中的每個字元，找出目標字母第一次出現在哪裡，記錄下來。
- 當目標字母再次出現，輸出間隔距離，並記下目前所在位置。
- 注意：指定字母「不分大小寫」。例如：輸入大寫 A ，那麼字串中的 A 和 a ，都要納入考量。

### 引導問題（點擊箭頭展開提示）

::: spoiler **Q. 能不能先將每個字元轉成大寫或小寫？**

A. 當然！我們可以使用內建的字元轉換函式，將傳進來的字元參數由小寫轉大寫，或是由大寫轉小寫。

使用`tolower()`，可將括弧內的字元轉成小寫字母。注意如果參數不是字母，或已經是小寫字母，就不會有任何變化。

使用`toupper()`，則可將括弧內的字元轉成大寫字母。參考範例：

char c;
c = toupper('m');
cout << c;  // 輸出 M
c = tolower(c);
cout << c;  // 輸出 m

:::
::: spoiler **Q. 如何判斷一個字母為大寫還是小寫？**

A. 有兩種方法：內建函式法與ASCII 距離判斷法。

* ==【法一】內建函式法==

常見的幾種字元分類函式如下：

| 函式名稱 | 說明 |
| --- | --- |
| `isalpha` | 判斷是否為英文字母 |
| `islower` | 判斷是否為小寫字母 |
| `isupper` | 判斷是否為大寫字母 |
| `isdigit` | 判斷是否為數字 |
| `isalnum` | 判斷是否為英文字母或數字 |

左方函式都有個共同特性：若符合條件，則回傳一非零整數。若不符合條件，則回傳 0 。

至於這些函式該如何使用呢？練習用關鍵字找答案，自己去google吧！答案都在那裡了！

* ==【法二】ASCII 距離判斷法==

如果忘記或懶得查詢內建函式怎麼用，以下為萬用方法。

我們從ASCII code table可以發現，0 到 9、A 到 Z、a 到 z，其 ASCII code都是連續的。因此，我們可以將兩個 ASCII code 直接相減，以差值判斷未知字元是哪一種字元。

char ch;
cin >> ch;
if(ch-'A' < 26){ // 與 A 的距離未滿26，代表 ch 為大寫
} else if(ch-'a' < 26){ // 與 a 的距離未滿26，代表 ch 為小寫
} else {// 其他輸入情況
}

請注意，以上程式適用的情況有限。像是輸入為 0 - 9，扣掉字母 A 的 ASCII code，結果為負數，在這個程式就會被誤判為大寫字母。
:::

## ROT13

### 解題步驟

- 使用`getline()`讀取一整行輸入字串。
- 檢查字串中的每個字元，判斷是大寫字母、小寫字母，還是其他字元（如：空白、逗點、句點）。
- 其他字元維持不變，大、小寫字母分別取代成13位之後的對應字母。

### 引導問題（點擊箭頭展開提示）

::: spoiler **Q. 如何將字串中每個字元「平移」一個特定數值？**

A. 舉例如下：

// ... 前略

string s = "This is a book!";
for(int i = 0; i < s.size(); i++)
    s[i] = s[i] + 5;  // 將每個字元都改成往後5個字元。
cout << s;  // 輸出字串為：Ymnx%nx%f%gttp&

// 後略...

:::
::: spoiler **Q. 題目提到「有需要時則重新繞回26英文字母開頭即可」，具體要怎麼繞？**

A. 我們先來解一個比較簡單的小任務：如何寫一個程式，將`ABCDEFGHIJKLMNOPQRSTUVWXYZ`往後平移 3 ，變成`DEFGHIJKLMNOPQRSTUVWXYZABC`？顯然，把 X, Y, Z變成 A, B, C，是解題的關鍵。我們就可以區分兩個子問題：

1) 如何判斷 ASCII code 會加到超過 Z？（想出**判斷式**）

2) 如何回到 A 之後，繼續加上沒加完的平移量？（想出**四則運算式**）

提示是上一題可以使用的 ASCII 距離判斷法，你可以運用加號和減號，直接將 `s[i]` 與 單一字元做運算。例如：`s[i] - ‘A’`，用以計算字串 s 的第 i 個字元，其 ASCII code 比字元`A`多多少。

以下程式有兩個地方打上`???`，請思考這兩個地方分別要填什麼，嘗試完成這個小任務。

string s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
for(int i = 0; i < s.size(); i++){
    s[i] += 3;
    if(???)  s[i] = ???;
}
cout << s;

這個小任務可以有好幾種做法。例如，有些人可能想要先將 ASCII code 平移到 0 ，再運用取商跟取餘數運算子，除以 26 進行一些運算，就不需判斷 ASCII code 相加有無超過，這樣也很好！

:::

## （延伸練習）跑長編碼與資料壓縮

### 引導問題

::: spoiler **Q. 可以直接`cin`每一行字串嗎？**

A. 觀察輸入說明及範例輸入，一長串連續的位元中，是否可能出現空格呢？如果保證每一行無空格，才能使用`cin`，否則就需要使用`getline()`函式來處理輸入。
:::

::: spoiler **Q. 如何判斷輸入是否為一個2進制位元串？**

A. 宣告一整數或布林型態的變數，再進入迴圈檢查。當遇到不是 0 或 1 的字元，要做什麼事情？當然，你也可以自定義一個函式（之後也會教），以回傳值代表是否為合理的2進制位元串。
:::
::: spoiler **Q. 4位元碼字是什麼東西？為什麼重複位元的長度用 3 個位元，會導致最大連續長度為 7？**

A. 需要先了解何謂二進位制，可以google一下。簡單來說，幾個位元就能夠表示 2 的幾次方個數字。從 0 開始的話， $n$ 個位元最大可以表示的數字為 $2^n - 1$。因此，重複位元的長度用 3 個位元，最大連續長度為 $2^3 - 1 = 7$。
:::
::: spoiler **Q. 重複位元最大連續長度為 7，會如何影響我寫的程式？**

A. 觀察範例測資中，前兩組測試資料。連續長度若超過 7，即使位元與前面相同，仍須重新統計，以下一組4位元碼字來表示。
:::
::: spoiler **Q. 我已經統計出重複次數，如何轉換為二進位制？**

A. 你可以使用：

* ==【法一】小孬孬法(窮舉)==

先求有再求好！因為重複字元很少，也就 7 種可能，可以使用選擇結構，根據重複次數輸出相應結果。

* ==【法二】進位轉換法==

上網搜尋 10 進位轉 2 進位的方式，發現規律後，嘗試以`while`迴圈搭配字串組合來完成任務。
:::