Bà Nội Đan Len
Problem
Mùa đông năm nay, bà nội của Mai quyết định đan cho cả nhà mỗi người một chiếc khăn len. Bà đan cả đời nên chẳng bao giờ viết công thức dài dòng. Thay vào đó, bà ghi vào cuốn sổ nhỏ những dòng ký hiệu rút gọn như thế này:
2[k3[p]]kMai lật sổ ra và mất cả buổi tối mới hiểu được quy tắc của bà:
- Mỗi chữ cái thường là một loại mũi đan. Ví dụ
klà mũi lên,plà mũi xuống. Bà có rất nhiều loại mũi nên dùng đủ cả bảng chữ cái. - Ký hiệu
n[S]nghĩa là đan đoạn \(S\) lặp lại đúng \(n\) lần liên tiếp. Trong đó \(n\) là một số nguyên dương, viết ngay trước dấu[và không có chữ số \(0\) ở đầu. - Đoạn \(S\) bên trong ngoặc cũng là một công thức, nên có thể chứa những cặp ngoặc khác lồng vào bên trong. Đoạn \(S\) cũng có thể rỗng (có lẽ bà ghi để nhắc mình... nghỉ tay uống trà).
Ví dụ, 2[k3[p]]k được khai triển như sau: 3[p] là ppp, nên k3[p] là kppp, lặp \(2\) lần thành kpppkppp, cuối cùng thêm một mũi k thành kpppkpppk.
Mai muốn nhập công thức vào chiếc máy đan tự động mới mua cho bà, nhưng máy chỉ hiểu dãy mũi đan đã được khai triển đầy đủ. Hãy giúp Mai viết chương trình khai triển công thức của bà nhé.
"Đan một mũi thì dễ, đan một trăm nghìn mũi theo đúng thứ tự mới là nghề."
-- Bà nội của Mai
Input
- Một dòng duy nhất chứa công thức \(s\) \((1 \leq |s| \leq 10^4)\), chỉ gồm chữ cái thường
a-z, chữ số và các dấu ngoặc vuông[,]. - Dữ liệu đảm bảo công thức hợp lệ theo quy tắc ở trên: các ngoặc được đóng mở đúng cặp, mỗi dấu
[đều đứng ngay sau một số \(n\) \((1 \leq n \leq 10^9)\), và mỗi số đều đứng ngay trước một dấu[. - Dữ liệu đảm bảo dãy mũi đan sau khi khai triển có độ dài từ \(1\) đến \(2 \times 10^5\).
Output
- In ra dãy mũi đan sau khi khai triển đầy đủ.
Sample
| # | Input | Output |
|---|---|---|
| 1 | | |
| 2 | | |
Note
Sample 1: 3[ab] là ab lặp \(3\) lần thành ababab, sau đó thêm c.
Sample 2:
3[yz]làyzyzyz, nênx3[yz]làxyzyzyz.2[x3[yz]]lặp đoạn trên \(2\) lần thànhxyzyzyzxyzyzyz.10[o]là \(10\) chữo(chú ý số lặp có thể có nhiều chữ số).
Code editor
Sign in to write and submit your solution.
Log in
Comments