Tính giá trị biểu thức cộng trừ

Nguồn: CLUE OJ Độ khó: Trung bình Duyệt xâu Tách số từ xâu

Đề bài

Cho xâu $S$ là một biểu thức chỉ gồm các số nguyên không âm và các dấu +, - (không có dấu cách, không có dấu ngoặc). Hãy tính giá trị của biểu thức, thực hiện các phép tính lần lượt từ trái sang phải.

Dữ liệu vào:

Một dòng duy nhất là xâu $S$.

Kết quả:

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

Giới hạn:

• $1 \le |S| \le 10^6$ ($|S|$ là độ dài xâu).
• $S$ bắt đầu và kết thúc bằng chữ số, giữa hai số luôn có đúng một dấu + hoặc -.
• Mỗi số có không quá $18$ chữ số và không có chữ số $0$ vô nghĩa ở đầu.
• Dữ liệu đảm bảo khi tính lần lượt từ trái sang phải, mọi kết quả trung gian và kết quả cuối cùng đều có giá trị tuyệt đối không vượt quá $9 \cdot 10^{18}$ (vừa kiểu số nguyên 64 bit).

Subtask:

• Subtask 1 (60% số điểm): $|S| \le 1000$ và mọi số đều không vượt quá $10^9$.
• Subtask 2 (40% số điểm): không có ràng buộc gì thêm.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

123+45-67+89

Ví dụ 1 – output

190

Ví dụ 2 – input

10-20

Ví dụ 2 – output

-10

• Ví dụ 1: $123 + 45 - 67 + 89 = 190$.
• Ví dụ 2: kết quả có thể là số âm.

Nguồn: phỏng theo bài "BIỂU THỨC" – vinhdinhcoder.net (chủ đề Xâu kí tự).

Lời mở đầu

Biểu thức như 123+45-67+89 được nhập vào dưới dạng một xâu. Muốn tính, ta phải tự "đọc" từng chữ số để ghép lại thành số, gặp dấu thì cộng hoặc trừ. Xâu dài tới $10^6$ kí tự nên cách làm phải là một lần duyệt từ trái sang phải. Ghi chú: đề gốc chỉ nói giá trị biểu thức vừa số nguyên 64 bit; mình ghi rõ thêm: mỗi số không quá 18 chữ số, không có số 0 ở đầu, và mọi kết quả trung gian cũng vừa 64 bit.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởngghép chữ sốLời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau. Test 1–12 là các biểu thức ngắn đánh vào từng trường hợp đặc biệt, test 13–20 là biểu thức dài gần $10^6$ kí tự.

Test	Nội dung kiểm tra
1–5	Ví dụ của đề, một số duy nhất (kể cả số 0), kết quả âm, toàn dấu trừ
6–7, 9–12	Kết quả vượt $2^{31}$ – dùng int bị tràn số
8, 10	Số 18 chữ số: $999\ldots9 - 999\ldots8 = 1$ – dùng double bị làm tròn sai
13–16	Biểu thức dài $10^6$ kí tự với hàng chục nghìn số – cắt xâu sau mỗi số sẽ quá thời gian
17–20	Biểu thức dài với các số cỡ $10^{18}$, kết quả trung gian tới $2 \cdot 10^{18}$

Ý tưởngDuyệt xâu một lần, ghép chữ số thành số

Ta đi qua từng kí tự của xâu và giữ 3 biến:

• so: số đang đọc dở. Gặp chữ số c thì so = so * 10 + (c - '0') – giống như viết thêm một chữ số vào bên phải.
• dau: dấu đứng trước số đang đọc ($+1$ hoặc $-1$). Số đầu tiên coi như có dấu $+$.
• ans: kết quả của các số đã đọc xong.

Khi gặp dấu + hoặc - nghĩa là số đang đọc đã kết thúc: cộng dau * so vào ans, đặt lại so = 0 và ghi nhớ dấu mới. Hết xâu thì nhớ chốt nốt số cuối cùng (vì sau nó không còn dấu nào).

Vì sao phải long long?

Mỗi số có thể tới 18 chữ số và kết quả trung gian tới $9 \cdot 10^{18}$ – vượt xa int (khoảng $2{,}1 \cdot 10^9$) nhưng vẫn vừa long long (khoảng $9{,}2 \cdot 10^{18}$). Không dùng double vì double chỉ giữ chính xác khoảng 15–16 chữ số.

Em nhập biểu thức rồi bấm Tiếp để xem từng số được tách ra và cộng/trừ vào kết quả:

s =

Ví dụ nhanh:

Lời giảiMột vòng for qua xâu

Đọc xâu bằng cin >> s (biểu thức không có dấu cách). Hai biến ans, so là long long.

C++▶ Chạy tay từng dòng codeDuyệt từng kí tự: chữ số thì ghép vào so, dấu thì chốt số vừa đọc.

Dữ liệu vào (stdin) – sửa thoải mái123+45-67+89

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. s[i] - '0' đổi kí tự chữ số thành số: mã của '7' trừ mã của '0' bằng 7.
2. Bản Python dùng mẹo: thay mỗi - bằng +- rồi tách theo +, mỗi mảnh là một số có dấu (ví dụ 10-20 → ["10", "-20"]), cộng tất cả lại.
3. Không được cắt xâu (s = s.substr(...)) sau mỗi số: mỗi lần cắt phải chép lại cả phần xâu còn lại, với $10^6$ kí tự sẽ rất chậm.

Không gian$O(|S|)$

Thời gian$O(|S|)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.023s. Bản Python đúng 20/20 test, chạy lâu nhất 0.107s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Dùng int cho ans và so	8/20	sai test 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20
Dùng double	13/20	sai test 8, 9, 10, 14, 17, 18, 19
Đọc xong mỗi số thì cắt xâu s = s.substr(p + 1)	16/20	sai test 13, 14, 15, 16
Tách từng số rồi đổi bằng stoi (chỉ cho int)	11/20	sai test 6, 8, 9, 10, 12, 14, 17, 18, 19

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.023s	Full điểm
	Python	20/20	0.107s	Full điểm
Dùng int	C++	8/20	–	Mất 12 test
Dùng double	C++	13/20	–	Mất 7 test
Cắt xâu mỗi lần	C++	16/20	–	Mất 4 test
Dùng stoi	C++	11/20	–	Mất 9 test

Ghi chú của mình: mẹo so = so * 10 + chữ số để ghép số từ các kí tự là kỹ năng nền tảng của chương xâu – em sẽ gặp lại nó trong rất nhiều bài "tách số từ xâu".

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇