solution

Trình phân tích cú pháp biểu thức (expression parser) của một trình biên dịch phải xử lý đúng nhiều mức độ ưu tiên và cả toán tử một ngôi. Trong bài này, quy ước độ ưu tiên (từ thấp đến cao) là: $\{+,-\}$ (kết hợp trái) $<$ $\{\times,\div\}$ (kết hợp trái) $<$ trừ một ngôi $<$ $\wedge$ (lũy thừa, kết hợp phải). Nói cách khác, toán tử trừ một ngôi chỉ áp dụng cho một số hạng hoặc một biểu thức trong ngoặc đơn ngay sau nó (được tính trước tiên), sau đó kết quả mới được dùng làm cơ số hoặc số mũ cho phép lũy thừa nếu có; ví dụ $-2\wedge2$ được hiểu là $(-2)\wedge2=4$, khác với $-(2\wedge2)=-4$ (muốn có $-4$ phải viết rõ dấu ngoặc).

Cho một biểu thức trung tố chỉ gồm số nguyên không âm (có thể nhiều chữ số, không có khoảng trắng bên trong một số), dấu ngoặc đơn, toán tử hai ngôi $+,-,\times,\div,\wedge$ (viết + - * / ^) và toán tử trừ một ngôi - (đặt ngay trước một số hoặc dấu (). Phép chia $\div$ là chia lấy phần nguyên hướng về 0. Biểu thức có thể chứa khoảng trắng tuỳ ý; số mũ (toán hạng bên phải của ^) trong các bộ test luôn không âm.

Hãy in ra biểu thức hậu tố tương đương (dùng ký hiệu ~ để biểu diễn toán tử trừ một ngôi, nhằm phân biệt với toán tử trừ hai ngôi -), các token cách nhau đúng một khoảng trắng, và giá trị của biểu thức (là số nguyên, có thể rất lớn, in đầy đủ không giới hạn độ dài, không dùng ký hiệu khoa học).

Ví dụ: -2^2*3+1 phân tích thành: $(-2)\wedge2=4$; $4\times3=12$; $12+1=13$. Hậu tố: 2 ~ 2 ^ 3 * 1 +. Giá trị: 13.