Một biểu thức toán học được nhập vào dưới dạng trung tố (infix), bao gồm:

• Các số nguyên không âm (không quá 3 chữ số),
• Các toán tử ~+~, ~-~, ~*~, ~/~ (chia lấy phần nguyên),
• Và dấu ngoặc đơn ~ ( ~ và ~ ) ~.

Hãy viết chương trình:

1. Chuyển đổi biểu thức từ dạng trung tố sang hậu tố (postfix),
2. Tính giá trị biểu thức hậu tố đó.

Giải thích:

• Trung tố: Toán tử nằm giữa hai toán hạng (ví dụ: ~3 + 5~),
• Hậu tố: Toán tử nằm sau hai toán hạng (ví dụ: ~3 5 +~).

Yêu cầu:

• Sử dụng stack để xử lý chuyển đổi và tính toán.
• Không có phép chia cho 0.

Input

• Một dòng chứa biểu thức trung tố hợp lệ, trong đó các phần tử được cách nhau bởi dấu cách.
• Biểu thức có không quá 100 phần tử (toán hạng, toán tử, dấu ngoặc).

Output

• Dòng đầu tiên là biểu thức hậu tố (các phần tử cách nhau bởi dấu cách),
• Dòng thứ hai là giá trị nguyên của biểu thức.

Ví dụ:

Input

( 3 + 5 ) * ( 2 - 1 )

Output

3 5 + 2 1 - *  
8