<div style="display: flex; justify-content: space-between;">
<a href="https://hackmd.io/@vientoligero/By_1qbKQp" style="margin-right: auto; color: grey; font-size: 14px;">上一頁 a001~a015</a>
</div>
# zerojudge基礎題庫題解 a017~
## 傳送門
* [a017 五則運算](#a017)
* [a020 身分證檢驗](#a020)
<a id=a017></a>
## zerojudge-a017 五則運算
### [題目](https://zerojudge.tw/ShowProblem?problemid=a017)
:::info
> 內容
計算五則運算式的結果,包含加、減、乘、除、餘
>輸入說明
輸入資料若干行直到 EOF 為止。每一行包含輸入一個字串,其中包含運算元及運算子,為了方便讀取,所有的運算子及運算元均以空格區隔。
運算元為 0 ~231 -1 的整數
運算子則包含 + - * / % 及 ( )
運算時請注意先乘除後加減及() 優先運算的計算規則
>輸出說明
對每一行輸入,輸出運算結果。
為了避免小數點誤差,所有的運算過程都不會產生小數點,可以放心使用整數進行運算
> 標籤
Stack, parser
:::
### 範例輸入&輸出
:::info
>範例輸入 #1
2 + 3 * 4
2 * ( 3 + 4 ) * 5
>範例輸出 #1
14
70
:::
### 題解
::: warning
#### Part0: 在看程式寫法之前,知道這些事會好理解一點...
1. 算式甚麼時候可以先算?
<table style="width:100%; border-collapse: collapse;">
<tr style="background-color: #EFEBD7;">
<th style="width: 25%; border: 1px solid #ddd; padding: 8px;">前面的運算子</th>
<th style="width: 25%; border: 1px solid #ddd; padding: 8px;">後面的運算子</th>
<th style="width: 25%; border: 1px solid #ddd; padding: 8px;">結果</th>
<th style="width: 25%; border: 1px solid #ddd; padding: 8px;">舉例</th>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">+, -</td>
<td style="border: 1px solid #ddd; padding: 8px;">+, -</td>
<td style="border: 1px solid #ddd; padding: 8px;">前面的<u>可以</u>先算</td>
<td style="border: 1px solid #ddd; padding: 8px;">1+3-2 = (1+3)-2</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">+, -</td>
<td style="border: 1px solid #ddd; padding: 8px;">*, /, %</td>
<td style="border: 1px solid #ddd; padding: 8px;">前面的<u>不可以</u>先算</td>
<td style="border: 1px solid #ddd; padding: 8px;">1+2*2 ≠ (1+2)*2</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">*, /, %</td>
<td style="border: 1px solid #ddd; padding: 8px;">+, -</td>
<td style="border: 1px solid #ddd; padding: 8px;">前面的<u>可以</u>先算</td>
<td style="border: 1px solid #ddd; padding: 8px;">3*2+8 = (3*2)+8</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">*, /, %</td>
<td style="border: 1px solid #ddd; padding: 8px;">*, /, %</td>
<td style="border: 1px solid #ddd; padding: 8px;">前面的<u>可以</u>先算</td>
<td style="border: 1px solid #ddd; padding: 8px;">3/2*3 = (3/2)*3</td>
</tr>
</table>
**結論**: **除了前面是+ -後面是\*/%之外,剩下的情況都可以先把前面的結果算出來,化簡算式**
2. 怎麼找到一個左括號所對應的右括號?
_(痾...先講... 這裡說的方法只是為了呼應下面的程式,方法有很多)_
這個規則應該用舉例得比較好理解,就請各位看看底下兩個算式的括號對應吧/ᐠ .ᆺ. ᐟ\ノ
* 第一個例子: <span style="background-color:#FFA07A;"><strong>(</strong></span> <span style="background-color: #D3D3D3;"><strong>(</strong></span> 3 + 12 <span style="background-color: #D3D3D3;"><strong>)</strong></span> + <span style="background-color: #E6E6FA;"><strong>(</strong></span> 2 * 8 <span style="background-color: #E6E6FA;"><strong>)</strong></span> + 6 <span style="background-color: #FFA07A;"><strong>)</strong></span> * <span style="background-color: #FFDAB9;"><strong>(</strong></span> 4 + 5 <span style="background-color: #FFDAB9;"><strong>)</strong></span>
* 第二個例子: <span style="background-color:#FFA07A;"><strong>(</strong></span> 1 + <span style="background-color: #D3D3D3;"><strong>(</strong></span> 2 + <span style="background-color: #E6E6FA;"><strong>(</strong></span> 3 + 4 <span style="background-color: #E6E6FA;"><strong>)</strong></span> <span style="background-color: #D3D3D3;"><strong>)</strong></span> <span style="background-color:#FFA07A;"><strong>)</strong></span>
**結論**: 從左往右找,**找到的右括號所對應的左括號就是它往左邊數的第一個左括號** (這個結論會建立在找到括號後有削掉,詳見註1)
_註1: 括號找到後就要把裡面的值算出來(即括號會消失)。所以第二個舉例的淺紫色右括號找到後,會把括號內的東西算出來,並且把淺紫色的括號給削掉。_
_<span style="background-color:#FFA07A;">(</span>1+<span style="background-color: #D3D3D3;">(</span>2+<span style="background-color: #E6E6FA;">(</span>3+4<span style="background-color: #E6E6FA;">)</span><span style="background-color: #D3D3D3;">)</span><span style="background-color:#FFA07A;">)</span> --><span style="background-color:#FFA07A;">(</span>1+<span style="background-color: #D3D3D3;">(</span>2+<span style="background-color: #E6E6FA;">7</span><span style="background-color: #D3D3D3;">)</span><span style="background-color:#FFA07A;">)</span>_
_這樣淺灰色括號才能依照這個規則消除_
<br>
#### Part1: 程式目的
這個解法就是不斷地在可以化簡(或是先算)時化簡算式,一直化簡到整個算式剩下一個數字,也就是答案
<br>
#### Part2: 先乘除餘後加減--權數定義
根據Part0-1,我們可以把`+-`的權數定義為1,`*/%`定義為2。這樣**只要後面符號的權數<=前面符號的權數,前面就可以先算了**。還有,因為符號可能會出現`(`,`(`是不能計算的,它的權數要定義成-1 (只要是小於1的數字都可以)。
<br>
#### Part3: 資料儲存--兩個Stack
因為要先乘除餘後加減,顯然把運算子和數字分開儲存是個好選擇。至於要用甚麼容器呢~ 不妨給Stack一個機會吧。因為用Stack會很好處理Part0-1**算式簡化**的部分。看到Part4你就懂了
在儲存資料的方面,我們可以用兩個Stack,分別儲存數字和運算子
<br>
#### Part4: 針對每一行測資,程式的運作流程
(以空白分隔),從左而右一一讀入 運算子/數字
如果讀入的東西是...
1. `數字`
* 直接加到nums stack即可
2. `+ - * / %`
* 重複直到(`opers stack空了 or 後面的權數比前面大`)為止。把前面可以先算的算完
_註1: `opers stack空了 or 後面的權數比前面大`的白話文就是`不能再化簡了`_
例如原本是nums={3, 2}, opers={\*},即3\*2。讀到+時,3\*2可以先算。先算的方法是 (1)pop兩個nums的元素 (2)pop一個opers的元素 (3)算完後把結果(`int`)丟回nums
* 化簡算式完後不要忘記把讀入的運算子加到opers中
3. ``(``
* 直接放到opers
4. ``)``
* 重複直到opers的頂部是`(`為止。一直抓出兩個數字,一個運算子,運算完把結果丟到nums。
_註1: 白話文: `把括號裡面的值算出來`_
* 讀完一行輸入後,最後不要忘記把剩下化簡過後的算式算完
可能有點難懂...請看Part5
<br>
#### Part5: 舉個例~~栗~~子
算式: $2~*~3 ~+~4~*~5~*~(~6~+~7~)$
<table style="width:100%; border-collapse: collapse;">
<tr style="background-color: #EFEBD7;">
<th style="width: 5%; border: 1px solid #ddd; padding: 8px;">Step</th>
<th style="width: 5%; border: 1px solid #ddd; padding: 8px;">讀入的東西</th>
<th style="width: 60%; border: 1px solid #ddd; padding: 8px;">採取行動</th>
<th style="width: 15%; border: 1px solid #ddd; padding: 8px;">nums stack</th>
<th style="width: 15%; border: 1px solid #ddd; padding: 8px;">opers stack</th>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">1</td>
<td style="border: 1px solid #ddd; padding: 8px;">2</td>
<td style="border: 1px solid #ddd; padding: 8px;">把2加到nums中</td>
<td style="border: 1px solid #ddd; padding: 8px;">{2}</td>
<td style="border: 1px solid #ddd; padding: 8px;">{}</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">2</td>
<td style="border: 1px solid #ddd; padding: 8px;">*</td>
<td style="border: 1px solid #ddd; padding: 8px;">沒法先算甚麼,把*加到opers中</td>
<td style="border: 1px solid #ddd; padding: 8px;">{2}</td>
<td style="border: 1px solid #ddd; padding: 8px;">{*}</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">3</td>
<td style="border: 1px solid #ddd; padding: 8px;">3</td>
<td style="border: 1px solid #ddd; padding: 8px;">把3加到nums中</td>
<td style="border: 1px solid #ddd; padding: 8px;">{2, <u>3</u>}</td>
<td style="border: 1px solid #ddd; padding: 8px;">{*}</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">4</td>
<td style="border: 1px solid #ddd; padding: 8px;">+</td>
<td style="border: 1px solid #ddd; padding: 8px;">先算2*3 即(2, 3, *)pop出來,把6丟回nums。再把+丟進opers</td>
<td style="border: 1px solid #ddd; padding: 8px;">{<u>6</u>}</td>
<td style="border: 1px solid #ddd; padding: 8px;">{<u>+</u>}</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">5</td>
<td style="border: 1px solid #ddd; padding: 8px;">4</td>
<td style="border: 1px solid #ddd; padding: 8px;">把4加到nums中</td>
<td style="border: 1px solid #ddd; padding: 8px;">{6, <u>4</u>}</td>
<td style="border: 1px solid #ddd; padding: 8px;">{+}</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">6</td>
<td style="border: 1px solid #ddd; padding: 8px;">*</td>
<td style="border: 1px solid #ddd; padding: 8px;">沒法先算,把*加到opers中</td>
<td style="border: 1px solid #ddd; padding: 8px;">{6, 4}</td>
<td style="border: 1px solid #ddd; padding: 8px;">{+, <u>*</u>}</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">7</td>
<td style="border: 1px solid #ddd; padding: 8px;">5</td>
<td style="border: 1px solid #ddd; padding: 8px;">把5加到nums中</td>
<td style="border: 1px solid #ddd; padding: 8px;">{6, 4, <u>5</u>}</td>
<td style="border: 1px solid #ddd; padding: 8px;">{+, *}</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">8</td>
<td style="border: 1px solid #ddd; padding: 8px;">*</td>
<td style="border: 1px solid #ddd; padding: 8px;">先算4*5,把20加到num。再把*加到opers</td>
<td style="border: 1px solid #ddd; padding: 8px;">{6, <u>20</u>}</td>
<td style="border: 1px solid #ddd; padding: 8px;">{+, <u>*</u>}</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">9</td>
<td style="border: 1px solid #ddd; padding: 8px;">(</td>
<td style="border: 1px solid #ddd; padding: 8px;">把(加到opers</td>
<td style="border: 1px solid #ddd; padding: 8px;">{6, 20}</td>
<td style="border: 1px solid #ddd; padding: 8px;">{+, *, <u>(</u>}</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">10</td>
<td style="border: 1px solid #ddd; padding: 8px;">6</td>
<td style="border: 1px solid #ddd; padding: 8px;">把6加到nums</td>
<td style="border: 1px solid #ddd; padding: 8px;">{6, 20, <u>6</u>}</td>
<td style="border: 1px solid #ddd; padding: 8px;">{+, *, (}</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">11</td>
<td style="border: 1px solid #ddd; padding: 8px;">+</td>
<td style="border: 1px solid #ddd; padding: 8px;">不能先算甚麼,把+加到opers</td>
<td style="border: 1px solid #ddd; padding: 8px;">{6, 20, 6}</td>
<td style="border: 1px solid #ddd; padding: 8px;">{+, *, (, <u>+</u>}</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">12</td>
<td style="border: 1px solid #ddd; padding: 8px;">7</td>
<td style="border: 1px solid #ddd; padding: 8px;">把7加到nums</td>
<td style="border: 1px solid #ddd; padding: 8px;">{6,20,6,<u>7</u>}</td>
<td style="border: 1px solid #ddd; padding: 8px;">{+, *, (, +}</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">13</td>
<td style="border: 1px solid #ddd; padding: 8px;">)</td>
<td style="border: 1px solid #ddd; padding: 8px;">一直抓出來..算..直到左括號為止。並pop掉(</td>
<td style="border: 1px solid #ddd; padding: 8px;">{6, 20, <u>13</u>}</td>
<td style="border: 1px solid #ddd; padding: 8px;">{+, *}</td>
</tr>
<tr style="background-color: #F4F0DC;">
<td style="border: 1px solid #ddd; padding: 8px;">14</td>
<td style="border: 1px solid #ddd; padding: 8px;">---</td>
<td style="border: 1px solid #ddd; padding: 8px;">一直抓出來..算..直到opers空為止</td>
<td style="border: 1px solid #ddd; padding: 8px;">{<u>266</u>}</td>
<td style="border: 1px solid #ddd; padding: 8px;">{}</td>
</tr>
<tr style="background-color: #EFEBD7;">
<td style="border: 1px solid #ddd; padding: 8px;text-align: center;" colspan="5"> ~end~ </td>
</tr>
</table>
輸出答案:$266$
:::
### Python
> 程式碼
```python=
import sys
def count(a, b, op): #a: int, b: int, c: str
if (op=='+'):
return a+b
if (op=='-'):
return a-b
if (op=='*'):
return a*b
if (op=='/'):
return a//b #題目有說除法不要留小數
if (op=='%'):
return a%b
return -999
def calculate(expr): #expr: str
exprs = expr.split() #把每個數字, 號分開來
opers = [] #裝str
nums = [] #裝int
prior = {'+':1, '-':1, '*':2, '/':2, '%':2, '(':-1}
for ele in exprs:
if ele=='(':
opers.append('(')
elif ele==')':
#算到左括號為止,照理講括號裡面會只剩下+-,頂多最後面(opers最前面)有一個*/%
while opers[-1] != '(':
#注意順序, nums的最前面會是比較晚加入的數字,也就是是計算時的第二個數字
val2 = nums.pop(); val1 = nums.pop();
op = opers.pop()
result = count(val1, val2, op)
nums.append(result)
opers.pop() #pop掉'('
elif ( ele in ['+', '-', '*', '/', '%'] ):
while (opers and prior[ele]<=prior[opers[-1]]):
#注意順序
val2 = nums.pop(); val1 = nums.pop();
op = opers.pop()
result = count(val1, val2, op)
nums.append(result)
opers.append(ele)
else: #ele是數字
nums.append( int(ele) )
while (opers): #把剩下的清掉,一樣,照理來講opers裡面會只剩下+-,頂多最前面有一個*/%
val2 = nums.pop(); val1 = nums.pop(); #注意順序
op = opers.pop()
result = count(val1, val2, op)
nums.append(result)
#這個時候,opers應該要是空的, nums剩下一個數字,就是答案
return nums[-1]
for inp in sys.stdin:
ans = calculate(inp)
print(ans)
```
_第20行的`return -999`: 那行程式其實可以不要寫,因為可以進去count的op一定是`+-*/%`其中一個。 只是,寫了可以比較好在debug (例如輸入 `1 + 1`跑出`-999`就知道那裏有問題了)_
> 作弊法——eval()
```python=
import sys
for inp in sys.stdin:
exp = inp.replace("/", "//") #題目有說無法整除用整數運算
print(eval(exp))
```
_註1: `eval()`可以塞算式進去給它算喔。_
_註2: `string.replace(oldstr, newstr, n)`會回傳 把`string`的前`n`個`oldstr`替換成`newstr` 的結果。如果不指定`n`是多少,就會全部替換。_
### C
> 程式說明
::: success
_(先嘆一口氣)_
1. 因為C內建沒有stack這種好東西,所以要自己用array來模擬。
我們可以建立一個大小足夠的陣列(下面稱array)來表示stack,在建立一個變數(`int`)表示目前stack的頂端在哪個位置。
例如stack長這樣: (右方為出入口)
<table style="width:100%; border-collapse: collapse;">
<tr style="background-color: #d9ead3;">
<td style="width: 12.5%; border: 1px solid #ddd; padding: 8px;">1</td>
<td style="width: 12.5%; border: 1px solid #ddd; padding: 8px;">2</td>
<td style="width: 12.5%; border: 1px solid #ddd; padding: 8px;">3</td>
<td style="width: 12.5%; border: 1px solid #ddd; padding: 8px;">4</td>
<td style="width: 12.5%; border: 1px solid #ddd; padding: 8px;">5</td>
<td style="width: 12.5%; border: 1px solid #ddd; padding: 8px;">6</td>
<td style="width: 12.5%; border: 1px solid #ddd; padding: 8px;">7</td>
<td style="width: 12.5%; border: 1px solid #ddd; padding: 8px;">←←</td>
</tr>
</table>
那用C模擬的stack就會長這樣
$array~~=~~\{1, 2, 3, 4, 5, 6, 7...\}~~~~~~idx=6$
在用C模擬stack時,常常運用到的指令如下:
<table style="width:100%; border-collapse: collapse;">
<tr style="background-color: #cbdac4;">
<th style="width: 50%; border: 1px solid #ddd; padding: 8px;">stack常使用到的指令</th>
<th style="width: 50%; border: 1px solid #ddd; padding: 8px;">用array模擬stack的寫法</th>
</tr>
<tr style="background-color: #d9ead3;">
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">設定變數a為stack最頂端的數值</td>
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">a = array[idx];</td>
</tr>
<tr style="background-color: #d9ead3;">
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">刪除stack最頂端的元素</td>
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">idx--;</td>
</tr>
<tr style="background-color: #d9ead3;">
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">添加x到stack的頂端</td>
<td style="width: 50%; border: 1px solid #ddd; padding: 8px;">idx++; array[idx]=x;</td>
</tr>
</table>
_註1: 有人可能會好奇...為何刪除頂端元素時`idx--`就夠了,不用做其他動作嗎? (例如把即將被移除的數字設成0之類的)_
_答案是 不用。雖然真正的stack在pop元素時,被pop掉的元素是直接記憶體間蒸發,消失的無影無蹤。 我們在用array模擬stack時,把`idx--`其實就可以當做本來的元素消失了 (~~aka無視~~)。為甚麼呢?_
_用array模擬的stack(在本程式)只有三個動作 ~~ **添加元素,看頂端的值,刪除元素**。 添加元素時,本來被pop掉的數字會被覆寫,看頂端的值根本不會動到它,刪除元素更不用說了。因此,被pop掉的元素就算還存在在array中,但是已經無稍食祿庸,自然不用加以更動、理會它了。_
<br>
2. C沒有map這種東西,在定義`+-*/%`的優先級時,要寫一個函式。
有寫a013羅馬數字的或許有用到。要寫一個滿滿的`switch-case`的函式
:::
>程式碼
```c=
#include <stdio.h>
#include <stdbool.h> //for bool
#include <string.h> //for strtok, strcspn
#include <stdlib.h> //for atoi
//和模擬Stack有關的東西
//建立stack的結構
typedef struct{
int val[5];
int top;
} numstack;
typedef struct{
char val[5];
int top;
} opstack;
//看stack是否為空
bool nums_emp(numstack* stack){
return (stack->top == -1);
}
bool ops_emp(opstack* stack){
return (stack->top == -1);
}
//加入一個數字到stack頂端
void nums_push(numstack* stack, int ele){
stack->top +=1;
stack->val[stack->top] = ele;
}
void ops_push(opstack* stack, char ele){
stack->top +=1;
stack->val[stack->top] = ele;
}
//刪除stack頂端元素
void nums_pop(numstack* stack){
stack->top -=1;
}
void ops_pop(opstack* stack){
stack->top -=1;
}
//回傳stack頂端的值
int nums_peek(numstack* stack){
return stack->val[stack->top];
}
char ops_peek(opstack* stack){
return stack->val[stack->top];
}
//其他的函式
//定義運算子的優先級
int prior(char op) {
switch(op) {
case '+':
case '-': return 1;
case '*':
case '/':
case '%': return 2;
default : return -1;
}
}
//計算算式的答案 (2數字1符號)
int count(int a, int b, char op){
switch(op){
case '+': return a+b; //return就會結束函式, 所以不用再break
case '-': return a-b;
case '*': return a*b;
case '/': return a/b;
case '%': return a%b;
default: return -999; //基本上不會走到default
}
}
//計算輸入測資的答案
int calculate(char expr[]) {
//宣告stack模擬版
numstack nums;
opstack opers;
nums.top = -1;
opers.top = -1;
char *token = strtok(expr, " "); //token: 指向char[]的指標
while (token != NULL) {
if (token[0] >= '0' && token[0] <= '9') { //token是數字
nums_push(&nums, atoi(token));
} else { //token是運算子or括號
char op = token[0];
if (op == '(') {
ops_push(&opers, op);
} else if (op == ')') {
//算到左括號為止,照理講括號裡面會只剩下+-,頂多最後面有一個*/%
while (ops_peek(&opers) != '(') {
//注意順序, nums最前面會是最晚加入的數字,也就是計算時的第二個數字
int val2 = nums_peek(&nums); nums_pop(&nums);
int val1 = nums_peek(&nums); nums_pop(&nums);
char op = ops_peek(&opers); ops_pop(&opers);
int result = count(val1, val2, op);
nums_push(&nums, result);
}
ops_pop(&opers); // 把'(' pop掉
} else { //是+-*/%其中一個
while (!ops_emp(&opers) && prior(ops_peek(&opers)) >= prior(op)){
//注意順序
int val2 = nums_peek(&nums); nums_pop(&nums);
int val1 = nums_peek(&nums); nums_pop(&nums);
char op = ops_peek(&opers); ops_pop(&opers);
int result = count(val1, val2, op);
nums_push(&nums, result);
}
ops_push(&opers, op);
}
}
token = strtok(NULL, " ");
}
//把剩下的清掉,一樣,照理來講opers裡面會只剩下+-,頂多最前面有一個*/%
while (!ops_emp(&opers)) {
//注意順序
int val2 = nums_peek(&nums); nums_pop(&nums);
int val1 = nums_peek(&nums); nums_pop(&nums);
char op = ops_peek(&opers); ops_pop(&opers);
int result = count(val1, val2, op);
nums_push(&nums, result);
}
//這個時候,opers應該要是空的, nums剩下一個數字,就是答案
return nums_peek(&nums);
}
int main() {
char expr[256]; // 拿來存輸入的
while (fgets(expr, sizeof(expr), stdin)) { //EOF處理
int npos = strcspn(expr, "\n");
expr[npos] = '\0'; //如果有\n 會把它換成\0
int ans = calculate(expr);
printf("%d\n", ans);
}
return 0;
}
```
_註1: `stack.val` 與 `stack->val`: 如果stack是結構(struct)本身就用前面的(`.`),如果是struct的指標就用後面的(`->`)_
_註2:`strcspn(待被偵測的字串A, 目標字元所組成的字串B)`: 會回傳字串A第一個目標字元的位置(`int`)。如果找遍整個字串A(碰到`\0`)都沒找到,會回傳_
_註3:`strtok(待分割字串,目標字元們所組成的字串 )`: strtok會從待分割字串的第一個字元開始擷取,擷到目標字元。把擷取的字串回傳(是以`指向char[]的char*`回傳喔),並把該目標字元改成`\0`。_
_如果要繼續擷取,要把`待分割的字串`改成`NULL`,即`strtok(NULL, 目標字元們所組成的字串)`。_
_想要知道strtok詳細機制的請詢問Google大神_
::: spoiler strtok舉例 因為有點占版面所以要看得請自行點開
```c
#include <string.h>
#include <stdio.h>
int main(){
char str[] = "I do love c so much";
char* token1 = strtok(str, "o");
printf("%s\n", token1); //token1是{'I', ' ', 'd', '\0'}
printf("%s\n", str); //str是{'I', ' ', 'd', '\0', ' ', ...} printf遇到\0就不印了
//要繼續抓 str要改NULL
char* token2 = strtok(NULL, "o");
printf("%s\n", token2); //token2:{' ', 'l', '\0'}
printf("%s\n", str); //str:{'I',' ','d','\0',' ','l','\0', ...}一樣遇到\0就不印了
//如果放str會...從頭開始抓
char* token3 = strtok(str, "o");
printf("%s\n", token3); //token3:{'I', ' ', 'd', '\0'}
printf("%s\n", str); //str:{'I',' ','d','\0',' ','l','\0', ...}一樣遇到\0就不印了
//token3會只有抓到"I d"是因為str的第三個字元(最最最最當初是o)已經被改成\0
//strtok遇到\0就不會往下抓了,直接返回當前擷取到的字串
}
```
:::
<br>
_註4: 第101行的`token[0]`: token是一個**字串**, token[0]是該字串的第一個**字元**。會把token的第一個字元抓出來的原因只有一個,就是字元才有ASCII碼,字串沒有。 (這個情況不用擔心數字字串的長度為多少,因為在這裡抓出第一個字元只是要判斷該字串是不是數字而已,沒有要幹嘛。)_
_註5: 因為算式會不斷地化簡。opers裡面最極端的情形也只不過是`{*, +, (, *, +}` (例如`3*4+(5*6+7)`)。所以兩個stack的長度只要開5個就夠了_
_註6: 第86行用`default`的原因: default其實是不可能被執行到的,因為會進去count的op本來就一定是`+-*/%`其中一個。寫了default可以從函式回傳的數值來看看程式有沒有bug(像是輸入`1 + 1`得到答案是`-999`就知道那裏有問題了)_
### C++
> 程式碼
```cpp=1
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <unordered_map>
using namespace std;
int count(int a, int b, char op){
switch (op){
case '+':
return a+b; //return就會結束函式, 所以不用再break
case '-':
return a-b;
case '*':
return a*b;
case '/':
return a/b;
case '%':
return a%b;
default: //基本上不可能走到default
return -999;
}
}
int calculate(string expr){
istringstream issexpr(expr);
//為了省麻煩,opers雖然只會放運算子(長度=1),但是用和下面的ele同資料型態的string
stack<string> opers;
stack<int> nums;
//理由同第33行註解,unordered_map用<string, int> (雖然char對記憶體比較友善)
unordered_map<string, int> prior =
{{"+", 1}, {"-", 1}, {"*", 2}, {"/", 2}, {"%", 2}, {"(", -1}};
string ele;
while (issexpr>>ele){
if (ele == "("){
opers.push("(");
}else if (ele == ")"){
//算到左括號為止,照理講括號裡面會只剩下+-,頂多最後面(opers最前面)有一個*/%
while(opers.top() != "("){
//注意順序, nums的最前面會是比較晚加入的數字,也就是計算時的第二個數字
int val2 = nums.top(); nums.pop();
int val1 = nums.top(); nums.pop();
char op = opers.top()[0]; opers.pop();
int result = count(val1, val2, op);
nums.push(result);
}
opers.pop(); //pop掉"("
}else if (ele=="+" || ele=="-" || ele=="*" || ele=="/" || ele=="%"){
while(!opers.empty() && prior[ele]<=prior[opers.top()]){
//注意順序
int val2 = nums.top(); nums.pop();
int val1 = nums.top(); nums.pop();
char op = opers.top()[0]; opers.pop();
int result = count(val1, val2, op);
nums.push(result);
}
opers.push(ele);
}else{ //else-->ele是數字
nums.push( stoi(ele) );
}
}
//把剩下的清掉,一樣,照理來講opers裡面會只剩下+-,頂多最前面有一個*/%
while (!opers.empty()){
//注意順序
int val2 = nums.top(); nums.pop();
int val1 = nums.top(); nums.pop();
char op = opers.top()[0]; opers.pop();
int result = count(val1, val2, op);
nums.push(result);
}
//這個時候,opers應該要是空的, nums剩下一個數字,就是答案
return nums.top();
}
int main(){
string inp;
while(getline(cin, inp)){ //EOF處理
int ans = calculate(inp);
cout << ans << endl;
}
return 0;
}
```
_註1: `std::istringstream`: 只能拿來讀取的stringstream,也就是它只能`>>`不能`<<`。_
_註2: `std::unordered_map`: 用法很像`std::map`,但是裡面的元素不會排序(因為是用哈希表 hash table),所以在查找的時候超快,時間複雜度是`O(1)`_
_註3: 第24行用`default`的原因: default其實是不可能被執行到的,因為會進去count的op本來就一定是`+-*/%`其中一個。寫了default可以從函式回傳的數值來看看程式有沒有bug(像是輸入`1 + 1`得到答案是`-999`就知道那裏有問題了),但其實還有一個原因是....為了避免下面那坨鬼東西出現_
```
main.cpp: In function ‘int count(int, int, char)’:
main.cpp:27:1: warning: control reaches end of non-void function [-Wreturn-type]
27 | }
| ^
```
_上面那個warning的意思就是說: 我的count函數有可能會沒回傳東西,導致錯誤。_
_註4: 第56, 71, 91行的`char op = opers.top()[0]; opers.pop();`: `opers.top()`是一個`string`,`op`被宣告為`char`變數。使用.`[0]`(回傳字串的第0個字元)可以把`"運算子"`(string)變成`'運算子'`(char)_
_註5: 第34, 38行的opers宣告與prior宣告: 這裡要把運算子宣告為`char`也是可以,但是就變成把`ele`(string)塞進opers時 和 放到prior看權數時要轉換成`char`_
### Java
> 程式碼
```java=1
import java.util.Scanner;
import java.util.Stack;
import java.util.HashMap;
public class Main{
private static int count(int a, int b, char op){
switch(op){
case '+':
return a+b; //return就會結束函式,這裡不用再break
case '-':
return a-b;
case '*':
return a*b;
case '/':
return a/b;
case '%':
return a%b;
default: //基本上不可能走到default
return -999;
}
}
private static int calculate(String expr){
Scanner exprscan = new Scanner(expr);
//為了省麻煩,opers雖然只會放運算子(長度=1),但是用和下面的ele同資料型態的String
Stack<String> opers = new Stack<>();
Stack<Integer> nums = new Stack<>();
//理由同第34行註解,HashMap用<String, Integer>(雖然Character對記憶體比較友善)
HashMap<String, Integer> prior = new HashMap<>();
prior.put("+", 1);
prior.put("-", 1);
prior.put("*", 2);
prior.put("/", 2);
prior.put("%", 2);
prior.put("(", -1);
while (exprscan.hasNext()){
String ele = exprscan.next();
if (ele.equals("(")){
opers.push("(");
}else if(ele.equals(")")){
//算到左括號為止
//照理講括號裡面會只剩下+-,頂多最後面(opers最前面)有一個*/%
while (!opers.peek().equals("(")){
//注意順序
//nums的最前面會是比較晚加入的數字,也就是是計算時的第二個數字
int val2 = nums.pop();
int val1 = nums.pop();
char op = opers.pop().charAt(0); //見註1
int result = count(val1, val2, op);
nums.push(result);
}
opers.pop(); //pop掉"("
}else if(prior.containsKey(ele)){ //true: ele是+-*/%其中一個
while(!opers.isEmpty()&&prior.get(ele)<=prior.get(opers.peek())){
//注意順序, nums的最前面會是計算時的第二個數字
int val2 = nums.pop();
int val1 = nums.pop();
char op = opers.pop().charAt(0);
int result = count(val1, val2, op);
nums.push(result);
}
opers.push(ele);
}else{ //true -->ele是數字
nums.push(Integer.parseInt(ele));
}
}
exprscan.close();
//把剩下的清掉,一樣,照理來講opers裡面會只剩下+-,頂多最前面有一個*/%
while (!opers.isEmpty()) {
//注意順序
int val2 = nums.pop();
int val1 = nums.pop();
char op = opers.pop().charAt(0);
int result = count(val1, val2, op);
nums.push(result);
}
//這個時候,opers應該要是空的, nums剩下一個數字,就是答案
return nums.pop();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextLine()) {
String inp = scanner.nextLine();
int ans = calculate(inp);
System.out.println(ans);
}
scanner.close();
}
}
```
_註1: 第64, 78, 99行的`char op = opers.pop().charAt(0);`: `opers.pop()`是一個`String`,`op`被宣告為`char`變數。使用`.chatAt(0)`(回傳字串的第0個字元)可以把`"運算子"`(String)變成`'運算子'`(char)_
_註2: 第25行用default的原因: default其實是不可能被執行到的,因為會進去count的op本來就一定是+-*/%其中一個。寫了default可以從函式回傳的數值來看看程式有沒有bug(像是輸入1 + 1得到答案是-999就知道那裏有問題了)_
_註3: 第35, 39行的opers宣告與prior宣告: 這裡要把運算子宣告為`Character`也是可以,但是就變成把`ele`(String)塞進opers時 和 放到prior看權數時要轉換成`Character`。_
<a id=a020></a>
## zerojudge-a020 身分證檢驗
### [題目](https://zerojudge.tw/ShowProblem?problemid=a020)
:::info
> 內容
我國的身分證字號有底下這樣的規則,因此對於任意輸入的身分證字號可以有一些基本的判斷原則,請您來判斷一個身分證字號是否是正常的號碼(不代表確有此號、此人)。
1. 英文代號以下表轉換成數字
<table style="width:100%; border-collapse: collapse;">
<tr>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">A=10 台北市</td>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">J=18 新竹縣</td>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">S=26 高雄縣</td>
</tr>
<tr>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">B=11 台中市</td>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">K=19 苗栗縣</td>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">T=27 屏東縣</td>
</tr>
<tr>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">C=12 基隆市</td>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">L=20 台中縣</td>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">U=28 花蓮縣</td>
</tr>
<tr>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">D=13 台南市</td>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">M=21 南投縣</td>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">V=29 台東縣</td>
</tr>
<tr>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">E=14 高雄市</td>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">N=22 彰化縣</td>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">W=32 金門縣</td>
</tr>
<tr>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">F=15 台北縣</td>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">O=35 新竹市</td>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">X=30 澎湖縣</td>
</tr>
<tr>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">G=16 宜蘭縣</td>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">P=23 雲林縣</td>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">Y=31 陽明山</td>
</tr>
<tr>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">H=17 桃園縣</td>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">Q=24 嘉義縣</td>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">Z=33 連江縣</td>
</tr>
<tr>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">I=34 嘉義市</td>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;">R=25 台南縣</td>
<td style="border: 1px solid #ddd; padding: 8px; background-color: #D6EAF4;"></td>
</tr>
</table>
2. 英文轉成的數字, 個位數乘9再加上十位數的數字
3. 各數字從右到左依次乘1、2、3、4....8
4. 求出(2),(3) 及最後一碼的和
5. (4)除10 若整除,則為 real,否則為 fake
例: T112663836
2 + 7\*9 + 1\*8 + 1\*7 + 2\*6 + 6\*5 + 6\*4 + 3\*3 + 8\*2 + 3\*1 + 6 = 180
除以 10 整除,因此為 real
>輸入說明
輸入共一行。每一行包含一組身分證號碼
>輸出說明
每讀入一行身分證字號,輸出 real or fake
> 標籤
字串處理
:::
### 範例輸入&輸出
:::info
> 範例輸入 #1
T112663836
> 範例輸出 #1
>
real
>範例輸入 #2
>
S154287863
>範例輸出 #2
>
fake
:::
### 題解
:::warning
這題還蠻簡單的,會有問題的應該是看不懂題目吧
#### Part1: 轉換規則:
身份證字號是由一個英文字母和九個數字組成,轉換規則如下:
1. 第一個英文字母轉換成一個二位數(參照表)後,把各位數字乘以9,並和十位數相加
2. 中間的八位數字由左而右分別\*8, \*7, \*6..., \*2, \*1
3. 最後一位數字 \*1
把1~3的結果相加起來 除以10看能不能整除
#### Part2: 範例測資用手算一次
範例測資1:
<table style="border-collapse: collapse;">
<tr>
<th style="background-color: #EFEBD7;">身分證字號</th>
<td colspan="2" style="text-align: center; background-color: #F4F0DC;">T</td>
<td style="background-color: #F4F0DC;"> </td>
<td style="background-color: #F4F0DC;">1</td>
<td style="background-color: #F4F0DC;">1</td>
<td style="background-color: #F4F0DC;">2</td>
<td style="background-color: #F4F0DC;">6</td>
<td style="background-color: #F4F0DC;">6</td>
<td style="background-color: #F4F0DC;">3</td>
<td style="background-color: #F4F0DC;">8</td>
<td style="background-color: #F4F0DC;">3</td>
<td style="background-color: #F4F0DC;"> </td>
<td style="background-color: #F4F0DC;">6</td>
</tr>
<tr>
<th style="background-color: #EFEBD7;">代表數字</th>
<td style="background-color: #F4F0DC;">2</td>
<td style="background-color: #F4F0DC;">7</td>
<td style="background-color: #F4F0DC;"> </td>
<td style="background-color: #F4F0DC;">1</td>
<td style="background-color: #F4F0DC;">1</td>
<td style="background-color: #F4F0DC;">2</td>
<td style="background-color: #F4F0DC;">6</td>
<td style="background-color: #F4F0DC;">6</td>
<td style="background-color: #F4F0DC;">3</td>
<td style="background-color: #F4F0DC;">8</td>
<td style="background-color: #F4F0DC;">3</td>
<td style="background-color: #F4F0DC;"> </td>
<td style="background-color: #F4F0DC;">6</td>
</tr>
<tr>
<th style="background-color: #EFEBD7;">要乘以幾</th>
<td style="background-color: #F4F0DC;">*1</td>
<td style="background-color: #F4F0DC;">*9</td>
<td style="background-color: #F4F0DC;"> </td>
<td style="background-color: #F4F0DC;">*8</td>
<td style="background-color: #F4F0DC;">*7</td>
<td style="background-color: #F4F0DC;">*6</td>
<td style="background-color: #F4F0DC;">*5</td>
<td style="background-color: #F4F0DC;">*4</td>
<td style="background-color: #F4F0DC;">*3</td>
<td style="background-color: #F4F0DC;">*2</td>
<td style="background-color: #F4F0DC;">*1</td>
<td style="background-color: #F4F0DC;"> </td>
<td style="background-color: #F4F0DC;">*1</td>
</tr>
</table>
相加結果: `180` -->是real
範例測資2:
<table style="border-collapse: collapse;">
<tr>
<th style="background-color: #EFEBD7;">身分證字號</th>
<td colspan="2" style="text-align: center; background-color: #F4F0DC;">S</td>
<td style="background-color: #F4F0DC;"> </td>
<td style="background-color: #F4F0DC;">1</td>
<td style="background-color: #F4F0DC;">5</td>
<td style="background-color: #F4F0DC;">4</td>
<td style="background-color: #F4F0DC;">2</td>
<td style="background-color: #F4F0DC;">8</td>
<td style="background-color: #F4F0DC;">7</td>
<td style="background-color: #F4F0DC;">8</td>
<td style="background-color: #F4F0DC;">6</td>
<td style="background-color: #F4F0DC;">3</td>
</tr>
<tr>
<th style="background-color: #EFEBD7;">代表數字</th>
<td style="background-color: #F4F0DC;">2</td>
<td style="background-color: #F4F0DC;">6</td>
<td style="background-color: #F4F0DC;"> </td>
<td style="background-color: #F4F0DC;">1</td>
<td style="background-color: #F4F0DC;">5</td>
<td style="background-color: #F4F0DC;">4</td>
<td style="background-color: #F4F0DC;">2</td>
<td style="background-color: #F4F0DC;">8</td>
<td style="background-color: #F4F0DC;">7</td>
<td style="background-color: #F4F0DC;">8</td>
<td style="background-color: #F4F0DC;">6</td>
<td style="background-color: #F4F0DC;">3</td>
</tr>
<tr>
<th style="background-color: #EFEBD7;">要乘以幾</th>
<td style="background-color: #F4F0DC;">*1</td>
<td style="background-color: #F4F0DC;">*9</td>
<td style="background-color: #F4F0DC;"> </td>
<td style="background-color: #F4F0DC;">*8</td>
<td style="background-color: #F4F0DC;">*7</td>
<td style="background-color: #F4F0DC;">*6</td>
<td style="background-color: #F4F0DC;">*5</td>
<td style="background-color: #F4F0DC;">*4</td>
<td style="background-color: #F4F0DC;">*3</td>
<td style="background-color: #F4F0DC;">*2</td>
<td style="background-color: #F4F0DC;">*1</td>
<td style="background-color: #F4F0DC;">*1</td>
</tr>
</table>
相加結果: `211` -->是fake
#### Part3: 知道這個程式可以簡潔一點
把英文字母轉換成數字後,整個身份證字號應該是一個11位數。把每一位分別乘以
`1, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1` 就可以算出答案了
:::
### Python
>程式說明
:::success
本程式用dict把身分證的第一個字母轉成數字
:::
> 程式碼
```python=
def check(elenum):
multi = [1, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1]
keynum = 0
for idx in range(11):
keynum += int(elenum[idx])*multi[idx]
if (keynum%10==0):
return "real"
else:
return "fake"
transform = {
'A':'10', 'B':'11', 'C':'12', 'D':'13', 'E':'14',
'F':'15', 'G':'16', 'H':'17', 'I':'34', 'J':'18',
'K':'19', 'L':'20', 'M':'21', 'N':'22', 'O':'35',
'P':'23', 'Q':'24', 'R':'25', 'S':'26', 'T':'27',
'U':'28', 'V':'29', 'W':'32', 'X':'30', 'Y':'31',
'Z':'33'}
citiid = input()
#先把11位數弄出來
first = citiid[0]
elevnums = citiid.replace(first, transform[first]);
#再把身分證字號轉成一個數字並判斷
ans = check(elevnums)
print(ans)
```
### C
>程式說明
:::success
C沒有map這種東西,在把英文字母轉換的時候可以用一個array(大小: 26)
array的第一個(`array[0]`)是放`'A'`對應對數字,第一個(`array[1]`)是放`'B'`對應的數字...。
要轉換的時候只要呼叫`a[ (要轉換的字母的ASCII) - ('A'的ASCII) ]`即可
:::
> 程式碼
```c=
#include <stdio.h>
char* check(char* elenum){
int multi[] = {1, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1};
int keynum = 0;
for (int idx=0; idx<11; idx++){
keynum+= (elenum[idx] - '0')*multi[idx];
}
if (keynum%10==0) return "real";
else return "fake";
}
int main(){
char* transform[] = {
"10", "11", "12", "13", "14",
"15", "16", "17", "34", "18",
"19", "20", "21", "22", "35",
"23", "24", "25", "26", "27",
"28", "29", "32", "30", "31",
"33"
};
/*
為了在同一個陣列做輸入&轉換成11個數字
所以citiid直接開11個,然後從第二個開始讀輸入
*/
char citiid[11];
scanf("%s", &citiid[1]);
//先把輸入轉換成11位數字
char* topcton = transform[ citiid[1]-'A' ]; //topcton: top char to num的縮寫
citiid[0] = topcton[0]; citiid[1] = topcton[1];
//再把身分證字號轉成一個數字並判斷
char* ans = check(citiid);
printf("%s", ans);
return 0;
}
```
_註1: 31~41行的補充: 舉例來講。假設今天輸入是`C888888888`, 那讀取輸入後citiid會是`{未定義, 'C', '8', '8'...}`_。轉換成11位數字時,定義topcton是指向`{'1', '2', '\0'}`的指標。這時剛好可以把`'1'`和`'2'`塞到`citiid[0]`(原先是`未定義`)`citiid[1]`(原先是`'C'`)。達成用一陣列完成讀取輸入跟轉成11位的目的。
_註2: 第12, 13行可以寫成`return (keynum % 10 == 0)? "real":"fake";`_
### C++
>程式說明
:::success
本程式用unordered把身分證的第一個字母轉成數字
:::
> 程式碼
```cpp=1
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
string check(string elenum){
int multi[] = {1, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1};
int keynum = 0;
for (int idx = 0; idx < 11; idx++) {
keynum += (elenum[idx] - '0') * multi[idx];
}
if (keynum%10==0) return "real";
else return "fake";
}
int main() {
unordered_map<char, string> transform = {
{'A', "10"}, {'B', "11"}, {'C', "12"}, {'D', "13"}, {'E', "14"},
{'F', "15"}, {'G', "16"}, {'H', "17"}, {'I', "34"}, {'J', "18"},
{'K', "19"}, {'L', "20"}, {'M', "21"}, {'N', "22"}, {'O', "35"},
{'P', "23"}, {'Q', "24"}, {'R', "25"}, {'S', "26"}, {'T', "27"},
{'U', "28"}, {'V', "29"}, {'W', "32"}, {'X', "30"}, {'Y', "31"},
{'Z', "33"}
};
string citiid; cin>>citiid;
//先把輸入轉換成11位數字
string elevnums = transform[citiid[0]] + citiid.substr(1);
//再把身分證字號轉成一個數字並判斷
string ans = check(elevnums);
cout << ans;
return 0;
}
```
_註1: 第16, 17行可以寫成`return (keynum % 10 == 0)? "real":"fake";`_
### Java
>程式說明
:::success
本程式用HashMap把身分證的第一個字母轉成數字
另外,初始化那個HashMap的程式碼有點長,所以開另一個函式寫
:::
> 程式碼
```java=1
import java.util.Scanner;
import java.util.HashMap;
public class Main{
private static String check(String elenum){
int[] multi = {1, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1};
int keynum = 0;
for (int idx=0; idx<11; idx++){
int number = Character.getNumericValue(elenum.charAt(idx));
int times = multi[idx];
keynum += number*times;
}
if (keynum % 10 == 0) return "real";
else return "fake";
}
private static String transToEleven(String nineid){
HashMap<Character, String> transform = new HashMap<Character, String>(){{
put('A', "10"); put('B', "11"); put('C', "12");
put('D', "13"); put('E', "14"); put('F', "15");
put('G', "16"); put('H', "17"); put('I', "34");
put('J', "18"); put('K', "19"); put('L', "20");
put('M', "21"); put('N', "22"); put('O', "35");
put('P', "23"); put('Q', "24"); put('R', "25");
put('S', "26"); put('T', "27"); put('U', "28");
put('V', "29"); put('W', "32"); put('X', "30");
put('Y', "31"); put('Z', "33");
}};
char first = nineid.charAt(0);
String result = transform.get(first) + nineid.substring(1);
return result;
}
public static void main(String args[]){
Scanner scanner = new Scanner(System.in);
String citiid = scanner.nextLine();
//先把輸入轉換成11位數字
String elevnums = transToEleven(citiid);
//再把身分證字號轉成一個數字並判斷
String ans = check(elevnums);
System.out.println(ans);
}
}
```
_註1: 第22行~32行的HashMap初始化: `{{}}`的初始化方式叫做**雙括號初始化**。就是個比較簡潔但是比較耗記憶體的初始化方式(所以其實傳統方法是比較好的)。想要了解詳細原理的請詢問Google大神。_