10/10/2018, 10:04

Giúp đỡ kiểm tra công thức toán học

Hi all,

Mình đang cần code xử lý để kiểm tra một chuỗi nhập vào có phải là công thức (toán học) hay ko? Mình định sử dụng RegEx để kiểm tra nhưng loay hoay mãi vẫn ko được. Có cao thủ nào về mục này không giúp mình với.

Các toán tử là (+), trừ (-), nhân (*), chia (/).
Các biến số là x, y, z.
Các hệ số đều là số nguyên.

Chú ý: Chỉ được sử dụng các ngoặc cong.

Ví dụ:
3*x + 6/y - (x + 3 * z) => Công thức đúng
3*x + (6/y - z*(x + 3 * z)) - (z/y)*(4*x) => Công thức đúng
3*x + (6/y - (x + 3 * z) => Công thức sai - thiếu ngoặc đóng

Help!!!!!!!!
jiSh@n viết 12:16 ngày 10/10/2018
Tìm hiểu về ký pháp nghịch đảo Ba Lan: http://en.wikipedia.org/wiki/Reverse_Polish_notation
fotech_nd viết 12:16 ngày 10/10/2018
Cảm ơn bạn nhưng đó là cách tính (mình cũng có rồi). Ý của mình là muốn kiểm tra xem một chuỗi nhập vào phải là một công thức đúng ko?

Ví dụ:
3*x + 6/y - (x + 3 * z) => Công thức đúng
3*x + (6/y - z*(x + 3 * z)) - (z/y)*(4*x) => Công thức đúng
3*x + (6/y - (x + 3 * z) => Công thức sai - thiếu ngoặc đóng
minhquan1712 viết 12:18 ngày 10/10/2018
cái này nếu bạn học về môn Compiler, phần phân tích grammar sẽ rất dễ xử lí. Bạn có thể tìm hiểu thêm ở đây.
http://en.wikibooks.org/wiki/Compiler_Construction
(chú trọng vào phần syntax analysis - đó là phần sẽ xử lí bài toán của bạn)
fotech_nd viết 12:09 ngày 10/10/2018
Cảm ơn bạn nhưng gợi ý của bạn phức tạp quá. Yêu cầu của mình rất đơn giản - chỉ là kiểm tra một công thức có đúng cú pháp hay ko thôi thôi (thực tế dự án của mình còn đơn giản hơn nữa ).

Liệu dùng RegEx có giải quyết được bài toán của mình ko nhỉ? Các cao thủ tiếp tục chỉ giúp với - Helpppppppppppp!
tiendx2002 viết 12:06 ngày 10/10/2018
Được gửi bởi fotech_nd
Hi all,

Mình đang cần code xử lý để kiểm tra một chuỗi nhập vào có phải là công thức (toán học) hay ko? Mình định sử dụng RegEx để kiểm tra nhưng loay hoay mãi vẫn ko được. Có cao thủ nào về mục này không giúp mình với.

Các toán tử là (+), trừ (-), nhân (*), chia (/).
Các biến số là x, y, z.
Các hệ số đều là số nguyên.

Chú ý: Chỉ được sử dụng các ngoặc cong.

Ví dụ:
3*x + 6/y - (x + 3 * z) => Công thức đúng
3*x + (6/y - z*(x + 3 * z)) - (z/y)*(4*x) => Công thức đúng
3*x + (6/y - (x + 3 * z) => Công thức sai - thiếu ngoặc đóng

Help!!!!!!!!
Regex có thể giải quyết vấn đề hay không thì mình không chắc nhưng có ý này.
PHP bản thân nó là 1 chương trình có năng lực xử lý ngôn ngữ rồi, nên có thể dùng cách eval để test, biến các x y z thành $x $y $z bằng replace và eval biểu thức
PHP Code:
eval('$x=3*$x+(6/$y-($x+3*$z);'); 
Trong ý này mình đã đưa thêm $ vào và xóa bỏ các dấu space.
Theo thông tin từ PHP http://php.net/manual/en/function.eval.php thì chỉ có thể có FALSE với lỗi parse error. Suy cho cùng đây chính là lỗi ta cần tìm. Để tránh division by zero có thể cần gán trước 1 số dữ liệu nào đó ngẫu nhiên. Tất nhiên có rất nhiều vấn đề cần giải quyết với nó nhưng không đủ thời gian cho câu trả lời hoàn hảo.
Thân ái.
jiSh@n viết 12:11 ngày 10/10/2018
Được gửi bởi fotech_nd
Cảm ơn bạn nhưng đó là cách tính (mình cũng có rồi). Ý của mình là muốn kiểm tra xem một chuỗi nhập vào phải là một công thức đúng ko?

Ví dụ:
3*x + 6/y - (x + 3 * z) => Công thức đúng
3*x + (6/y - z*(x + 3 * z)) - (z/y)*(4*x) => Công thức đúng
3*x + (6/y - (x + 3 * z) => Công thức sai - thiếu ngoặc đóng
Bạn ko hiểu vấn đề rồi. Để tính được 1 biểu thức thì trước hết bạn cần phải parse được nó ra dạng-có-thể-tính-được. Thế nào là 1 biểu thức đúng? Làm sao để biết 1 biểu thức có đúng hay ko nếu bạn ko "xử lý" nó?

Regex chỉ có thể đối sánh với 1 pattern có sẵn. Bạn có thể tạo ra 1 pattern chuẩn dành cho các biểu thức toán học ko? Đừng nói tới pattern chuẩn, chỉ riêng xác định formal language và lập automat cho biểu thức toán học đã là ko dễ dàng rồi.

Bạn cần tự xây dựng cho mình 1 parser, hoặc có thể nhờ vả 1 parser có sẵn là PHP như cách mà tiendx2002 đề nghị.
fotech_nd viết 12:16 ngày 10/10/2018
Được gửi bởi tiendx2002
Regex có thể giải quyết vấn đề hay không thì mình không chắc nhưng có ý này.
PHP bản thân nó là 1 chương trình có năng lực xử lý ngôn ngữ rồi, nên có thể dùng cách eval để test, biến các x y z thành $x $y $z bằng replace và eval biểu thức
PHP Code:
eval('$x=3*$x+(6/$y-($x+3*$z);'); 
Trong ý này mình đã đưa thêm $ vào và xóa bỏ các dấu space.
Theo thông tin từ PHP http://php.net/manual/en/function.eval.php thì chỉ có thể có FALSE với lỗi parse error. Suy cho cùng đây chính là lỗi ta cần tìm. Để tránh division by zero có thể cần gán trước 1 số dữ liệu nào đó ngẫu nhiên. Tất nhiên có rất nhiều vấn đề cần giải quyết với nó nhưng không đủ thời gian cho câu trả lời hoàn hảo.
Thanks bác Tiến nhưng với cách này nếu làm đơn giản thì rất nguy hiểm cho hê thống vì chuỗi là mình là một chuỗi do User nhập vào (nếu họ nhập một cách bình thường thì ko sao nhưng nếu họ nhập vào những dòng lệnh phá hệ thống thì rất nguy), nên việc phải kiểm tra đâu là những lệnh, toán tử hợp lệ cũng đã rất phức tạp rồi.

Regards!

[=========> Bổ sung bài viết <=========]

Được gửi bởi jiSh@n
Bạn ko hiểu vấn đề rồi. Để tính được 1 biểu thức thì trước hết bạn cần phải parse được nó ra dạng-có-thể-tính-được. Thế nào là 1 biểu thức đúng? Làm sao để biết 1 biểu thức có đúng hay ko nếu bạn ko "xử lý" nó?

Regex chỉ có thể đối sánh với 1 pattern có sẵn. Bạn có thể tạo ra 1 pattern chuẩn dành cho các biểu thức toán học ko? Đừng nói tới pattern chuẩn, chỉ riêng xác định formal language và lập automat cho biểu thức toán học đã là ko dễ dàng rồi.

Bạn cần tự xây dựng cho mình 1 parser, hoặc có thể nhờ vả 1 parser có sẵn là PHP như cách mà tiendx2002 đề nghị.
Thanks bạn đã nhiệt tình , mình cũng đã hỏi thêm một số người nữa - đúng là đa phần đều phải sử dụng thuật toán balan đảo ngược để kiểm tra, mình đã hiểu cơ chế rồi nhưng để viết được thì chắc chắn là ko hề đơn giản với mình - hic. Mình muốn một thuật toán đơn giản hơn nhưng có vẻ là khó .
tiendx2002 viết 12:07 ngày 10/10/2018
Được gửi bởi fotech_nd
Thanks bác Tiến nhưng với cách này nếu làm đơn giản thì rất nguy hiểm cho hê thống vì chuỗi là mình là một chuỗi do User nhập vào (nếu họ nhập một cách bình thường thì ko sao nhưng nếu họ nhập vào những dòng lệnh phá hệ thống thì rất nguy), nên việc phải kiểm tra đâu là những lệnh, toán tử hợp lệ cũng đã rất phức tạp rồi.
Với các biểu thức dạng đơn giản thì nó sẽ không có hơn 2 ký tự A..z liền nhau nên xử dễ. Không có từ khóa câu lệnh nào chỉ có từ 2 ký tự trở xuống. Dùng regex cắt bỏ tất cả những ký tự "thừa".
Tuy nhiên đồng ý là xử lý như vậy khá rắc rối, cái ta cần có lẽ chỉ là 1 đoạn script kiểm tra tính đóng mở hợp lệ của ngoặc. Theo mình đây là lỗi thông dụng nhất và cũng khó phát hiện bằng mắt hơn các lỗi khác.
Thân ái.
Bài liên quan
0