Tính giá trị biểu thức toán học
Đề bài
Cho một xâu biểu thức toán học chứa các toán hạng là các số nguyên có giá trị nằm trong đoạn $-10^{18}$ đến $10^{18}$ và các toán tử là các phép tính cộng (+), trừ (-), nhân (*) và các dấu ngoặc đơn () quy định việc ưu tiên. Mỗi phần tử sẽ cách nhau bởi 1 khoảng trắng, riêng dấu ngoặc đơn sẽ viết liền theo số.
Ví dụ ta có biểu thức toán học như sau: (3 + (2 * 5)) - (2 + 3) * 4
Kết quả của biểu thức toán học trên sẽ là:
$(3 + (2 \cdot 5)) - (2 + 3) \cdot 4$
$= (3 + 10) - 5 \cdot 4$
$= 13 - 20$
$= -7$
Hãy xử lý tính toán đúng theo quy luật toán học để trả ra kết quả sau cùng là số nguyên duy nhất là đáp án.
Input: Xâu biểu thức toán học có độ dài tối đa $2 \cdot 10^6$.
Output: Một số nguyên duy nhất là kết quả của biểu thức toán học.
Ràng buộc:
- 30% điểm đầu tiên có độ dài xâu tối đa 50 và giá trị các toán hạng trong đoạn $[0, 50]$.
- 30% điểm tiếp theo có độ dài xâu tối đa $10^4$.
- 40% điểm còn lại không có giới hạn gì thêm.
(3 + (2 * 5)) - (2 + 3) * 4-7- Số âm viết liền dấu trừ:
-32là một toán hạng âm, còn phép trừ luôn là dấu-đứng riêng có khoảng trắng hai bên. Ví dụ17 - -32nghĩa là $17 - (-32)$. Vậy dấu-mà ngay sau là chữ số thì là dấu của số. - Subtask 1 ghi toán hạng trong $[0, 50]$ nhưng test thật vẫn có số âm (toán hạng nằm trong $[-55, 84]$) – code phải đọc được số âm ngay từ subtask 1.
- Kết quả rất lớn: từ subtask 2, toán hạng tới $10^{18}$ và nhân với nhau nên đáp án dài tới 245 chữ số – không có kiểu số nguyên có sẵn nào của C++ chứa nổi, phải tự cài số nguyên lớn.
Lời mở đầu
Tính giá trị biểu thức có ngoặc và thứ tự ưu tiên là ứng dụng "kinh điển" của ngăn xếp: dùng hai ngăn xếp, một cho các số, một cho các toán tử. Bài này còn "cài" thêm một cái bẫy: kết quả cực lớn. Mình sẽ làm 2 bước: cách 1 dùng long long để nắm chắc thuật toán (ăn subtask 1), cách 2 giữ nguyên thuật toán, chỉ thay long long bằng số nguyên lớn tự cài để full điểm.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
| Test | Độ dài xâu | Số toán hạng | Giá trị toán hạng | Đáp án | Đáp án vừa long long |
|---|---|---|---|---|---|
| 1 – 30 | 37 … 48 | 7 … 9 | -55 … 84 | 1 … 6 chữ số | 30/30 |
| 31 – 60 | 9.670 … 9.785 | 697 … 740 | $\approx -10^{18}$ … $10^{18}$ | 68 … 173 chữ số | 0/30 |
| 61 – 100 | 1.963.250 … 1.964.504 | 144.180 … 144.730 | $\approx -10^{18}$ … $10^{18}$ | 143 … 245 chữ số | 0/40 |
- 100 test, khớp đúng 3 mức điểm 30% – 30% – 40% của đề: test 1–30 ngắn (dưới 50 ký tự), test 31–60 khoảng $10^4$ ký tự, test 61–100 gần $2 \cdot 10^6$ ký tự (khoảng 144 nghìn toán hạng).
- Chỉ test 1–30 có đáp án vừa
long long. Từ test 31 trở đi đáp án dài hàng chục tới hàng trăm chữ số. - Ngoặc lồng nhau trong bộ test chỉ sâu tối đa 2 tầng, nhưng thuật toán ngăn xếp bên dưới đúng với độ sâu bất kỳ.
Các subtask khớp với bộ test như sau (ô ghi số test đúng của từng cách – chạy thật, bản C++):
| Subtask | Điều kiện (theo đề) | Các test | Cách 1 long long | Cách 2 số lớn |
|---|---|---|---|---|
| 1 (30%) | độ dài $\le 50$, toán hạng trong $[0, 50]$ | 1 – 30 | 30/30 | 30/30 |
| 2 (30%) | độ dài $\le 10^4$ | 31 – 60 | 0/30 | 30/30 |
| 3 (40%) | độ dài $\le 2 \cdot 10^6$ | 61 – 100 | 0/40 | 40/40 |
Ý tưởngHai ngăn xếp: một cho số, một cho toán tử
Khi đọc biểu thức từ trái sang phải, gặp một toán tử ta chưa tính ngay được vì chưa biết phía sau có phép nhân (ưu tiên hơn) hay dấu ngoặc hay không. Vậy ta "cất tạm" nó vào ngăn xếp, và chỉ tính khi chắc chắn đã đến lúc:
- Gặp số → đẩy vào ngăn xếp số
num. - Gặp
(→ đẩy vào ngăn xếp toán tửop(làm "vách ngăn"). - Gặp
)→ tính liên tục cho tới khi đỉnhoplà(, rồi bỏ(đi. Lúc này cả cặp ngoặc đã được thay bằng 1 số. - Gặp toán tử t (
+ - *) → trong khi đỉnhoplà toán tử có độ ưu tiên ≥ t thì tính nó trước; sau đó đẩy t vào. - Hết xâu → tính nốt các toán tử còn lại. Số còn lại trong
numlà đáp án.
num (số lấy ra trước là vế phải b, sau là vế trái a) và 1 toán tử trên đỉnh op, đẩy kết quả a op b trở lại num.Vì sao "≥" chứ không phải ">"? Với các phép cùng mức như 10 - 3 - 2, ta phải tính từ trái sang: $(10 - 3) - 2 = 5$. Khi gặp dấu - thứ hai, dấu - thứ nhất có cùng độ ưu tiên nên phải tính trước. Nếu dùng ">" ta sẽ tính thành $10 - (3 - 2) = 9$ – sai!
Em nhập biểu thức (các phần tử cách nhau bởi dấu cách, ngoặc viết liền số như đề) rồi bấm Tiếp để xem hai ngăn xếp làm việc:
Cách 1Hai ngăn xếp với long long – subtask 1
Cài đặt đúng thuật toán trên, các số lưu bằng long long. Mình đọc cả dòng bằng getline rồi duyệt từng ký tự.
- Điều kiện nhận biết số:
isdigit(c) || (c == '-' && isdigit(s[i + 1]))– dấu trừ dính liền chữ số là dấu âm của số, còn dấu trừ đứng riêng (sau nó là dấu cách) là phép trừ. - Đọc số xong,
iđang ở ký tự sau chữ số cuối cùng, nên phảii--để vòngfortăng lại đúng chỗ. - Trong hàm
tinh(): lấybtrước rồi mới lấya, vìađược đẩy vào trước. Với phép trừ, nhầm thứ tự là ra sai dấu ngay. - Điều kiện
op.top() != '('trong vòngwhilecủa toán tử: không được tính "xuyên qua" dấu mở ngoặc – phần trong ngoặc phải đợi tới khi gặp).
Kết quả chạy thật: bản C++ đúng 30/100 test, chạy rất nhanh (lâu nhất 0.061s) nhưng sai kết quả ở toàn bộ test 31–100 vì tràn số: ví dụ test 31 máy in ra một số 19 chữ số "vô nghĩa" trong khi đáp án thật dài 74 chữ số. Thuật toán đúng, chỉ có kiểu dữ liệu không đủ chỗ.
print(eval(input()))! Mình chạy thử: đúng 60/100 test, nhưng ở test 61–100 bị lỗi RecursionError – biểu thức hơn 144 nghìn toán hạng quá dài khiến trình biên dịch của Python bị tràn đệ quy. Mẹo vui để kiểm tra, nhưng không thay được thuật toán đâu nhé.Cách 2Giữ thuật toán, đổi sang số nguyên lớn – full
Phần tính biểu thức giữ nguyên như cách 1, chỉ thay long long bằng kiểu Big tự cài. Mình lưu số lớn như cách các bạn tính tay trên giấy, nhưng mỗi "chữ số" là một khối 9 chữ số thập phân (hệ cơ số $10^9$), cộng thêm một cờ am cho dấu:
- Cộng hai số cùng dấu: cộng trị tuyệt đối (có nhớ), giữ dấu. Khác dấu: lấy trị tuyệt đối lớn trừ nhỏ (có mượn), dấu theo số có trị tuyệt đối lớn hơn.
- Trừ: $a - b = a + (-b)$ – chỉ cần đổi dấu $b$ rồi dùng lại phép cộng.
- Nhân: nhân "đặt tính" từng khối với nhau; dấu kết quả âm khi hai số khác dấu. Tích hai khối nhỏ hơn $10^{18}$ nên cộng thêm số nhớ vẫn vừa
long long. - Hàm
chuanHoabỏ các khối 0 thừa ở đầu và quy ước số 0 luôn không âm (tránh in ra-0).
taoSocắt chuỗi chữ số thành từng khối 9 chữ số từ phải sang trái.inSoin khối cao nhất bình thường, các khối sau phải in đủ 9 chữ số (thêm số 0 ở đầu) bằngsetw(9) << setfill('0').- Bản Python không cần cài gì thêm vì số nguyên của Python vốn là số lớn – code Python chỉ là cách 1 viết lại, có tách token bằng biểu thức chính quy
-?\d+|[-+*()].
Kết quả chạy thật: bản C++ đúng 100/100 test, lâu nhất 0.069s; bản Python đúng 100/100 test, lâu nhất 0.353s.
Tuy kết quả cuối dài cả trăm chữ số, phần lớn các phép tính chỉ làm trên số 1–2 khối (toán hạng $\le 10^{18}$), nên tổng thời gian vẫn rất nhỏ.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất (test đúng) | Ghi chú |
|---|---|---|---|---|
| 1. Hai ngăn xếp, long long | C++ | 30/100 | 0.003s | Sai (tràn số) ở test 31–100 |
| 2. Hai ngăn xếp, số lớn | C++ | 100/100 | 0.069s | Full điểm |
| Python | 100/100 | 0.353s | Full điểm | |
Mẹo eval | Python | 60/100 | 0.026s | Lỗi RecursionError ở test 61–100 |
uuTien và tinh; (2) luôn đọc kỹ giới hạn: toán hạng $10^{18}$ mà có phép nhân thì long long chắc chắn không đủ.
Nhận xét
Đăng nhận xét