Centre for Gifted Education - Hanoi university of Technology

Một ngăn xếp là một cấu trúc dữ liệu dạng thùng chứa (container) của các phần tử (thường gọi là các nút (node)) và có hai phép toán cơ bản : push and pop. Push bổ sung một phần tử vào đỉnh (top) của ngăn xếp,nghiã là sau các phần tử đã có trong ngăn xếp. Pop giải phóng và trả về phần tử đang đứng ở đỉnh của ngăn xếp. Trong stack, các đối tượng có thể được thêm vào stack bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào sau cùng mới được phép lấy ra khỏi stack.

Ngoài ra, stack cũng hỗ trợ một số thao tác khác:

isEmpty(): Kiểm tra xem stack có rỗng không.

Top(): Trả về giá trị của phần tử nằm ở đầu stack mà không hủy nó khỏi stack. Nếu stack rỗng thì lỗi sẽ xảy ra.

Ứng dụng:

Cho 1 biểu thức với các số nguyên và các phép toán số học + - x /.

Hình vẽ mô tả 1 stack:

Hint:

Chuyển biểu thức sang dạng hậu tố ( postfix ). Dùng 1 stack để lưu kết quả trung gian

Bước 1: Khởi tạo stack rỗng.

Bước 2: Đọc các phần tử của biểu thức từ trái sang phải. Kiểm tra:

Nếu nó là 1 số thì đẩy nó vào stack

Nếu nó là 1 phép toán thì lấy từ stack ra 2 giá trị. Tỉnh nó bằng phép toán đó rồi lại cho vào stack.

Cuối cũng stack còn duy nhất 1 phần tử đó là kết quả của biểu thức.

Input

Gồm 1 dòng ghi biểu thức cần tính toán

Output

Ghi ra kết quả của biểu thức

Example

Input:
(1+2)x3-5

Output:
4