Link Sub: http://www.spoj.com/PTIT/problems/PTIT121E/
Người Gửi: Sai
- Problem:
Hóa chất chỉ gồm các nguyên tố C, H, O có trọng lượng 12,1, 16 tương ứng. Nó được biểu diễn dạng "nén", ví dụ COOHHH là CO2H3 hay CH (CO2H) (CO2H) (CO2H) là CH(CO2H)3.
Nếu ở dạng nén thì số lần lặp >=2 và <=9. Tính khối lượng hóa chất.
Input
Gồm một dòng mô tả hóa chất không quá 100 kí tự chỉ gồm C, H, O, (, ), 2,..,9.
Output
Khối lượng của hóa chất (luôn <=10000).
Example:
Khối lượng của hóa chất (luôn <=10000).
Input
COOH
Output:
45
Input
CH(CO2H)3
Output:
148
Input
((CH)2(OH2H)(C(H))O)3
Output:
222
- Solution:
Bài này có nhiều cách:
- Cách 1: Dùng stack:
+ Mỗi một kí tự sẽ thêm vào stack giá trị của nó: C -> 12, H -> 1, O -> 16.
+ Khi gặp kí tự '(' thì push vào con 0 (Mục đích là để ngăn cách);
+ Khi gặp kí tự ')' thì tính tổng tất cả giá trị (+ xóa từng giá trị) từ đỉnh cho tới con 0 đầu tiên gặp. (Cái này giống như gộp phần tử). Xóa nốt con 0 và push vào giá trị tổng vừa tính.
+ Khi gặp kí tự từ 2->9: Lấy giá trị ở đầu và nhân với trị số rồi lại push vào stack.
+ Cuối cùng duyệt lại stack và tính tổng các phần tử trong stack.
- Cách 2: (Admin): Dùng phương pháp trâu: Tìm con '(' và tìm con ')' tương ứng. coppy xâu trong cặp ngoặc đó rồi lặp số lần chỉ số của nó (nếu có) gán vào cuối xâu. Có nghĩa là: Sẽ chuyển toàn bộ cụm công thức hóa thành các cụm công thức đơn lẻ: VD: CH3(COOH)2 -> CH3COOHCOOH. Tham khảo cách 2 Click vào đâyInput
CH(CO2H)3
Output:
148
Input
((CH)2(OH2H)(C(H))O)3
Output:
222
- Code:
C++:
https://ideone.com/FRWxHM
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main ()
{
string xau;
cin>>xau;
stack <int> s;
int ktAdd=0;
for (int i=0; i<xau.length(); i++)
{
if (xau[i]=='(')
{
s.push(0);
}
else if (xau[i]==')')
{
int tmp=0;
while (!s.empty() && s.top()!=0)
{
tmp+=s.top();
s.pop();
}
if (!s.empty() && s.top()==0)
{
s.pop();
s.push(tmp);
}
}
else if (xau[i]>='0' && xau[i]<='9')
{
int so=xau[i]-'0';
if (!s.empty())
{
int tmp = s.top();
s.pop();
tmp = tmp * so;
s.push(tmp);
} else
{}
}
else if (xau[i]=='C')
{
s.push(12);
}
else if (xau[i]=='H')
{
s.push(1);
}
else if (xau[i]=='O')
{
s.push(16);
}
}
int S=0;
while (!s.empty())
{
S+=s.top();
s.pop();
}
cout<<S;
return 0;
}