Giả sử chúng ta có một công thức hóa học; chúng ta phải tìm số lượng của từng nguyên tử.
Một nguyên tử hóa học luôn bắt đầu bằng chữ hoa, có thể có không hoặc nhiều chữ thường theo sau, đại diện cho tên. Và 1 hoặc nhiều chữ số đại diện cho số lượng của nguyên tử đó có thể theo sau nếu số lượng lớn hơn 1. Nhưng nếu số lượng là 1, không có chữ số nào theo sau. Ví dụ, H2O và H2O2 đều hợp lệ, nhưng H1O2 là không hợp lệ.
Vì vậy, nếu đầu vào giống như Na2(CO)3, thì đầu ra sẽ là C3Na2O3, điều này cho thấy 3 Carbon (C), 2 Sodium (Na), 3 Oxygen (O).
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau −
Định nghĩa hàm makeRet(), nhận một map m,
ret := chuỗi rỗng
cho mỗi cặp khóa-giá trị 'it' trong m −
ret := ret + khóa của it
nếu giá trị của it > 1, thì −
ret := ret + giá trị của it dưới dạng chuỗi
trả về ret
Định nghĩa hàm countOfAtoms(), nhận s,
Định nghĩa một map m
Định nghĩa một ngăn xếp st
i := 0, n := kích thước của s
khi i < n, thực hiện −
c := s[i]
(tăng i lên 1)
nếu c bằng '(', thì −
chèn m vào st
m := Định nghĩa một map
ngược lại khi c bằng ')', thì −
val := 0
khi (i < n và s[i] trong khoảng 0 đến 9), thực hiện −
val := val * 10 + (s[i] - ASCII của '0')
(tăng i lên 1)
Định nghĩa một map temp := phần tử đỉnh của st
xóa phần tử khỏi st
cho mỗi cặp khóa-giá trị 'it' trong m −
giá trị của it := giá trị của it * val
temp[khóa của it] := temp[khóa của it] + giá trị của it
m := temp
Ngược lại
name := chuỗi rỗng
val := 0
name := name + c
khi (i < n và s[i] trong khoảng 'a' đến 'z'), thực hiện −
name := name + s[i]
(tăng i lên 1)
khi (i < n và s[i] trong khoảng 0 đến 9), thực hiện −
val := val * 10 + (s[i] - ASCII của '0')
(tăng i lên 1)
val := (nếu val bằng 0, thì 1, ngược lại val)
m[name] := m[name] + val
trả về makeRet(m)
Hãy xem triển khai sau để hiểu rõ hơn −
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: string makeRet(map<string, int> m){ string ret = ""; for (auto& it : m) { ret += it.first; if (it.second > 1) { ret += to_string(it.second); } } return ret; } string countOfAtoms(string s){ map<string, int> m; stack<map<string, int> > st; int i = 0; int n = s.size(); while (i < n) { char c = s[i]; i++; if (c == '(') { st.push(m); m = map<string, int>(); } else if (c == ')') { int val = 0; while (i < n && s[i] >= '0' && s[i] <= '9') { val = val * 10 + (s[i] - '0'); i++; } map<string, int> temp = st.top(); st.pop(); for (auto& it : m) { it.second *= val; temp[it.first] += it.second; } m = temp; } else { string name = ""; int val = 0; name += c; while (i < n && s[i] >= 'a' && s[i] <= 'z') { name += s[i]; i++; } while (i < n && s[i] >= '0' && s[i] <= '9') { val = val * 10 + (s[i] - '0'); i++; } val = val == 0 ? 1 : val; m[name] += val; } } return makeRet(m); } }; main(){ Solution ob; cout << (ob.countOfAtoms("Na2(CO)3")); } Đầu vào
Na2(CO)3
Đầu ra
C3Na2O3