## 例題-a017. 五則運算
[題目連結](https://zerojudge.tw/ShowProblem?problemid=a017)
這題給定五個運算子 "$+\ -\ *\ /\ \%$" 、前後括號跟多個數字，再給定運算式，問**最後運算結果**
首先有幾個重點要先說明
1. 運算子的優先順序是 $*\ /\ \%$ > $+\ -$，而括號內為**最優先**運算，其餘由左到右
2. 題目給定數字在 $0\sim2^{31}$，所以要用 long long int
3. 運算過程或結果可能出現**負數**，例: 0 - 3 - 1
4. 多個括號可以**包含**或**並排**，例: ( ( 1 + 0 ) + ( 1 + 1 ) * ( 8 % 2 ) )
最後給一組測資，可以測試你的程式碼對不對 (ZJ 上面大神給的)
* ( 8 % 2 * ( 3 + 2 + 1 ) / ( 2 * 2 ) ) - 6 - 3 + 4 - ( 1 - ( 50 * 2 ) ) + 6
* 答案 : 100
接著開始這次的題目解析，首先題目都是一行行輸入，在 python 當中很方便
但如果是 C++ 就需要用到 getline，如果不會的可以先去看[這段](https://hackmd.io/t8lc_fV3T9qOUf48QRe-Og?view#%E5%AD%97%E4%B8%B2%E9%95%B7%E5%BA%A6)
其實一個運算式當中，有很多個元素，題目當中是用空格將其隔開
所以用 stringstream 處理，他可以把元素用空白分割，取出特定值
再來處理優先順序的問題，先考慮**最優先的括號**，我把括號內當作一個整體
因為**括號內可能還有括號**，所以這題需要用到**遞迴**，只要把前後也加上一個括號
那整行輸入其實就是一個整體，所以一個函式可以重複使用，可以看看下面的例子
"$(\ (\ 1\ +\ 5\ )\ *\ 3\ /\ 2\ )$" ，很明顯如果要處理當中的元素，我們要先考慮
"$(\ 1\ +\ 5\ )$" 應該要回傳 $6$，後面才能計算 $6\ *\ 3\ /\ 2$
所以如果遇到 "("，就要**開啟新的整體 $A$ (新的遞迴)**，並且是從 "(" 的下一位開始
如果遇到 ")" 代表**現在這個整體 $A$ 結束**，要計算目前整體的答案，並回傳給**上一個**整體
接者處理 $*\ /\ \%$，在運算的過程中，每次運算都要有兩個數字 $n_1,\ n_2$
比如遇到運算子 "$*$"，就可以把 $n_1$ 跟 $n_2$ 替換成 $n_1*n_2
$1\ +\ 3\ *\ 4\ *\ 5$ 就可以先變成 $1\ +\ 12\ *\ 5$ 再變成 $1\ +\ 60$
至於 $n_1,\ n_2$ 乃至於所有數字的儲存，都可以放到 stack 當中
會使用 stack 的原因是 stack 是先進後出，所以**先出來**的就是**最晚放**進去的
我們遇到 $*\ /\ \%$ 運算子時，第一個取出來的就是 $n_1$，而 $n_2$ 是在 $*\ /\ \%$ 的後面一位
比如上面圖片例子中，遇到 "$*$" 時 stack 是 $\{6\}$，所以第一個取出來的數字是 $6$
也就是計算中的 $n_1$，而 $n_2$ 是 "$*$" 後面一格，所以記得要用 global index 紀錄
才能很方便地在多層遞迴當中都使用同一個 index
但要注意 $n_2$ 有可能是一個數字或是一個整體，一個整體如果單看一格就是左括號 "("
如果是整體，就進行更深一層的遞迴，直到把這次整體算出來，也就是**遇到括號右括號**
最後才是所謂的 $+$ 跟 $-$，注意左到右的計算過程已經被 index $0\sim len$ 解決
在最後 stack 可能會剩下一些數字，比如下面這個例子中的 $(\ 1\ +\ 5\ )$
這個整體(遞迴)中 stack 應該是 $\{1,5\}$，過程中應該要記錄 $+$ $-$ 符號，**最後才能計算**
要注意，因為用 stack 一定要從**後面**開始計算，所以會遇到一些問題
假設數字是 $\{1,1,2\}$，符號是 $\{-,-\}$，算式應該是 $1-1-2$
但是如果從**後面**開始計算，順序會如下
* $n_1=1,\ n_2=2 \rightarrow n_1-n_2=1-2=-1$
* $n_1=1,\ n_2=-1\rightarrow n_1-n_2=1-(-1)=2$
最後跑出來答案是 $2$，跟算式的解 $-2$ 不同，很明顯有問題
因為從後面開始計算違反了 "由左到右計算" 這個優先條件
此時我給了三個簡單的作法
1. 捨棄 stack 特性，直接用迴圈由左往右解
2. 把 $n_1$ 固定為 stack$[0]$
3. 設立假想數字 $x$
其中第二項跟第三項是比較像的，第一項太簡單我就不贅述了
如果 $n_1$ 一直是 stack$[0]$，那整個式子從 $1-1-2$ 變成 $1-2-1$
很明顯第一項以後的計算順序調換不會有任何問題
第三項是用一個假想數字當作 $n_1$，我們假設每個式子都有一個假想數字 $0$
所以式子當中不論遇到 $+$ 或是 $-$，都會變成這樣 $0 + 1$、$0 - 1$
這樣 $1-1-2$ 就可以拆成 $0-2$，$-2-1$，$-3+1$ $-2$
就跟最初算式的答案一樣，只是要記得跟stack$[0]$ 相加
```cpp=
#include<bits/stdc++.h>
using namespace std ;
typedef long long LL ;
int len, idx ; // 總元素數量、目前位置
vector<string> objs ; // 放整個字串(其中是分割的各個元素)
LL recursion() {
LL n1, n2 ;
stack<LL> stk1 ; // 放數字
stack<char> stk2 ; // 放符號
while (idx < len) { // 判斷符號
if (objs[idx] == ")") {
idx++ ; // 記得要往下走
break ;
}
else if (objs[idx] == "(")
++idx, stk1.push(recursion()) ;
else if (objs[idx] == "+")
stk2.push('+'), idx++ ;
else if (objs[idx] == "-")
stk2.push('-'), idx++ ;
else if (objs[idx] == "*") { // 需要 n2
n1 = stk1.top() ; stk1.pop() ;
if (objs[++idx] == "(") // n2 是一個括號(運算式)
++idx, n2 = recursion() ;
else // n2 是數字
n2 = stoi(objs[idx++]) ;
stk1.push(n1*n2) ;
}
else if (objs[idx] == "/") { // 需要 n2
n1 = stk1.top() ; stk1.pop() ;
if (objs[++idx] == "(") // n2 是一個括號(運算式)
++idx, n2 = recursion() ;
else // n2 是數字
n2 = stoi(objs[idx++]) ;
stk1.push(n1/n2) ;
}
else if (objs[idx] == "%") { // 需要 n2
n1 = stk1.top() ; stk1.pop() ;
if (objs[++idx] == "(") // n2 是一個括號(運算式)
++idx, n2 = recursion() ;
else // n2 是數字
n2 = stoi(objs[idx++]) ;
stk1.push(n1%n2) ;
}
else // 數字
stk1.push(stoi(objs[idx++])) ;
}
stk1.push(0) ; // 假想數字
while (stk1.size() > 2) {
n1 = stk1.top() ; stk1.pop() ; // 從後面計算的總和
n2 = stk1.top() ; stk1.pop() ; // 真實數字
if (stk2.top() == '+') // 需要加真實數字
stk1.push(n1+n2) ;
else // 需要減真實數字
stk1.push(n1-n2) ;
stk2.pop() ; // 用完符號了
}
n2 = stk1.top() ; stk1.pop() ;
n1 = stk1.top() ; stk1.pop() ;
stk1.push(n1+n2) ; // 剩下的假想數字跟第一位數字總和
return stk1.top() ;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
string s, obj ; // 一行的字串、單一元素字串
LL ans ;
while (getline(cin, s)) {
objs = {}, idx = 0 ; // 初始化
if (s.empty()) // 遇到 EOF
break ;
s += " )" ; // 幫助遞迴結尾
stringstream ss(s) ; // 以空白做分割
while (ss >> obj)
objs.push_back(obj) ; // 把每個元素存到 vector
len = objs.size() ; // 元素數量
ans = recursion() ;
cout << ans << '\n' ;
}
return 0 ;
}
```
## 不同子集合的相同總和
給定兩個整數 $n, m$，還有 $n$ 個 $0\sim9$ 的數字
問這 $n$ 個數字是否可以分成 $m$ 組，並且這 $m$ 組內的元素總和皆相同
如果可以，就輸出每個組別的元素(依照該組最小元素做排序，元素由小到大)
如果不能，就輸出 "No"
範例測資 :
7 4
4 3 2 3 5 2 1
範例輸出 :
1 4
2 3
2 3
5
範例測資 :
6 5
1 1 1 1 1 1
範例輸出 :
No
解題思路 :
首先我們可以先把遞迴的部分放到後面思考，先想想一個組別的元素總和應該是多少
因為總共有 $n$ 個數字與 $m$ 組，假設 $n$ 個數字總和是 $X$，一組就會是 $\frac{X}{m}$ (因各組總和相同)
如果 $X$ 不能整除 $m$，就代表無法分成 $m$ 組，所以就可以直接輸出 "No" 了
接下來說明一下如何進行遞迴找出所有組別，首先最直觀的就是枚舉
透過枚舉可以將不同組合的可能列舉出來，只要找出符合答案的結果就可以
```cpp=
#include<bits/stdc++.h>
using namespace std ;
vector<int> v ;
vector<bool> used ;
vector<int> ans ; // 第 i 個元素在第 ans[i] 組
int n, m, x ; // x 代表分組後各組內元素總和(皆相同以 x 表示)
int rec(int now, int cnt) {
// 目前總和 now，已經分了 cnt 組
if (now == x) {
cnt ++ ;
now = 0 ;
}
else if (now > x) // 超過必不可能
return -1 ;
if (cnt == m)
return m ;
int get ;
for (int i=0;i<n;i++) {
if (i && v[i] == v[i-1] && !used[i-1])
continue ;
if (!used[i]) {
used[i] = true ; // 選
ans[i] = cnt+1 ;
get = rec(now+v[i], cnt) ;
if (get == m)
return m ;
used[i] = ans[i] = 0 ; // 去除跑過的
if (get == -1)
break ;
}
}
return 0 ;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
cin >> n >> m ;
v.resize(n) ;
used.resize(n) ;
ans.resize(n) ;
int sum = 0 ;
for (int i=0;i<n;i++) {
cin >> v[i] ;
sum += v[i] ;
used[i] = ans[i] = 0 ;
}
if (sum % m) {
cout << "No\n" ;
return 0 ;
}
x = sum / m ;
sort(v.begin(), v.end()) ;
if (v[0] > x) {
cout << "No\n" ;
return 0 ;
}
if (rec(0, 0) != m) {
cout << "No\n" ;
return 0 ;
}
cout << "Yes\n" ;
map<int, vector<int>> mp ;
for (int i=0;i<n;i++)
mp[ans[i]].push_back(v[i]) ;
for (auto& it: mp) {
for (int& i: it.second)
cout << i << ' ' ;
cout << '\n' ;
}
return 0 ;
}
```
Sign in with Wallet
Connect another wallet