Tách toán tử toán hạng trong chuỗi
TIL
610
regular expression
8
White

Tuấn Nguyễn viết ngày 17/05/2018

Vấn đề

Hôm nay mình ngồi làm project Calculator trong FreeCodeCamp cần implement thuật toán tính biểu thức trung vị. Nhưng trước hết có vấn đề nho nhỏ là tách toán tử toán hạng trong chuỗi. Ví dụ như sau:
Chuỗi đầu vào: 1+(2/3x6+3)+2.3x8+2.4
Kết quả đầu ra: ["1", "+", "(", "2", "/", "3", "x", "6", "+", "3", ")", "+", "2.3", "x", "8", "+", "2.4"]

Giải quyết

Tách từ chuỗi ra mảng nên ta nghĩ tới hàm split. Cái khó ở đây là truyền separator. Ta quen truyền separator đơn giản rồi còn phức tạp như này ta cần đến sức mạnh của RegExp.
Ta có 2 cách:
Cách 1:
Separator sẽ là các toán tử. Hàm split sẽ giữ cả các các separator. Ví dụ str.split(/([+-x/()])/). Bạn chú ý cắp dấu ( ) ngay sau / / thể hiện hàm split sẽ giữ các separator thay vì bỏ chúng đi.
Cách này sẽ ổn với các biểu thức ko có ngoặc nhọn. Ví dụ alt text
Nhưng với biểu thức ban đầu có ngoặc nhọn sẽ bị thừa các kí tự rỗngalt text
Do găp separator liên tiếp là + và ( nên nó tách kí tự rỗng như trên.
Công việc sau đó rất đơn giản. Dùng fitler để filter các kí tự rỗng đó đi.
Cách 2:
Separator chuẩn chỉ hơn sẽ các các đường dứt nét trong hình vẽalt text
Các đường gạch này trước hoặc sau các toán tử. Do đó hàm split là: str.split(/(?<=[-+x/()])|(?=[-+x/()])/)
Chú ý cặp ngoặc tròn () ở đây không có nghĩa là hàm split sẽ giữ lại separator nữa mà nó là một phần của RegExp
Cụ thể (?<=[-+x/()]) có nghĩa là những chỗ mà các toán tử đứng trước alt text

Còn (?=[-+x/()]) có nghĩa những chỗ mà toán tử đứng sau
alt text
Kết hơp bởi | ta được separator hoàn chỉnh. Và kết quả chuẩn chỉ, ta không cần lọc nữa.
alt text
Bạn tham khảo https://docs.microsoft.com/en-us/dotnet/standard/base-types/regular-expression-language-quick-reference để rõ hơn về RegExp.

Kết luận

2 cách đều không quá dài. Cách thứ nhất dễ nghĩ biểu thức reg hơn. Tuy nhiên lại thêm một bước. Cách thứ 2 khó nghĩ hàm reg hơn.
Sau bước này, bạn có thể áp dụng stack để tính biểu thức nói trên.

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Tuấn Nguyễn

4 bài viết.
1 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
2 3
Đặt vấn đề Khi viết RestApi ta chỉ thường chọn một số thông tin để truyền về client. Ví dụ như thông tin user thì không cần truyền password chẳng ...
Tuấn Nguyễn viết 2 tháng trước
2 3
White
1 0
Khái niệm Data Flow Testing là kĩ thuật kiểm thử sử dụng Control Flow Graph (CFG) để tìm ra những nguy cơ tiềm tàng cho việc sử dụng dữ liệu. Ví d...
Tuấn Nguyễn viết 5 tháng trước
1 0
Bài viết liên quan
White
0 2
fCC: Technical Documentation Page note So I have finished the HTML part of this exercise and I want to come here to lament about the lengthy HTML ...
HungHayHo viết 2 tháng trước
0 2
White
19 1
Toán tử XOR có tính chất: + A XOR A = 0 + 0 XOR A = A Với tính chất này, có thể cài đặt bài toán sau với độ phức tạp O(N) về runtime, và với O(1)...
kiennt viết gần 2 năm trước
19 1
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
4 bài viết.
1 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!