Bài 37.14. Máy Tính Biểu Thức Cơ Bản - [Độ khó: Siêu khó]

Bạn được giao nhiệm vụ phát triển một máy tính biểu thức đơn giản. Máy tính này có thể xử lý các biểu thức số học chỉ chứa các số nguyên không âm, phép cộng (+), phép trừ (-), phép nhân (*), phép chia nguyên (/), và dấu ngoặc đơn (). Biểu thức được cung cấp dưới dạng một chuỗi. Bạn cần phân tích chuỗi này, chuyển đổi nó thành dạng trung tố (infix) rồi tính toán giá trị cuối cùng. Để lưu trữ các thành phần của biểu thức (số, toán tử), bạn có thể sử dụng danh sách liên kết.

INPUT FORMAT

Một dòng duy nhất chứa chuỗi S là biểu thức cần tính. Độ dài của S không vượt quá 200 ký tự. Biểu thức hợp lệ, không có lỗi cú pháp. Các số nguyên không âm, có thể có nhiều chữ số. Ví dụ: (12+3)*4-5/1.

OUTPUT FORMAT

In ra một số nguyên duy nhất là kết quả của biểu thức.

Ví dụ:

Input:

(10+20)*3-4/2

Output:

88

Giải thích:

• Biểu thức là (10+20)*3-4/2.
• Ưu tiên ngoặc: (10+20) = 30. Biểu thức trở thành 30*3-4/2.
• Ưu tiên nhân/chia từ trái sang phải:
  • 30*3 = 90. Biểu thức trở thành 90-4/2.
  • 4/2 = 2. Biểu thức trở thành 90-2.
• Cuối cùng là phép trừ: 90-2 = 88.
• Kết quả là 88.

Ví dụ 2 (Edge Case):

Input:

1

Output:

1

Giải thích:

• Biểu thức chỉ có một số, kết quả là chính nó.