Bộ máy tính biểu thức hậu tố

Bối cảnh và bài toán

Một bộ điều khiển nhận biểu thức ở dạng hậu tố (Reverse Polish Notation). Mỗi token là một số nguyên hoặc một trong ba toán tử +, -, *. Dữ liệu luôn tạo thành một biểu thức hợp lệ và mọi kết quả trung gian nằm trong long long.

Yêu cầu

Tính giá trị của biểu thức hậu tố.

Input

• Dòng 1: số token m.
• Dòng 2: m token cách nhau bởi khoảng trắng.

Output

In giá trị của biểu thức.

Ràng buộc

• 1 <= m <= 2 * 10^5
• Mỗi toán hạng có trị tuyệt đối <= 10^9
• Biểu thức hợp lệ và kết quả trung gian vừalong long``

Chấm điểm

Ví dụ 1

Input

3
2 3 +

Output

5

Giải thích. Đưa 2, 3 vào ngăn xếp rồi lấy hai số để cộng.

Ví dụ 2

Input

5
5 2 3 * +

Output

11

Giải thích. Tính 2*3=6, sau đó 5+6=11.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.