Phân tích phương trình toán học cơ bản cho phần mềm giáo dục của trẻ em?

Question

Lấy cảm hứng từ một số recent TED talk, tôi muốn viết một phần nhỏ của phần mềm giáo dục. Nhà nghiên cứu đã tạo ra một số máy tính thu nhỏ trong hình dạng của các khối gọi là "Siftables".

alt text http://images.ted.com/images/ted/tedindex/embed-posters/DavidMerrill-2009.embed_thumbnail.jpg
[David Merril, inventor - with Siftables in the background.]

Có rất nhiều ứng dụng ông sử dụng các khối trong nhưng yêu thích của tôi là khi mỗi khối là một số hoặc biểu tượng hoạt động cơ bản. Sau đó bạn có thể sắp xếp lại các khối số hoặc ký hiệu hoạt động trong một dòng, và nó sẽ hiển thị một câu trả lời trên một khối có thể thay đổi khác.

alt text http://i44.tinypic.com/m7us6g.png

Vì vậy, tôi đã quyết định rằng tôi muốn thực hiện một phiên bản phần mềm của "Math Siftables" trên thang điểm hạn chế như dự án cuối cùng của tôi cho một CS dĩ nhiên là tôi đang tham gia.

Cách được chấp nhận chung để phân tích cú pháp và diễn giải một chuỗi các biểu thức toán học là gì và nếu chúng hợp lệ, hãy thực hiện thao tác?

Đây có phải là trường hợp tôi nên triển khai trình phân tích cú pháp/lexer đầy đủ không? Tôi sẽ tưởng tượng việc giải thích các biểu thức toán học cơ bản sẽ là một vấn đề bán phổ biến trong khoa học máy tính vì vậy tôi đang tìm kiếm một cách đúng đắn để tiếp cận vấn đề này.

Ví dụ, nếu khối Math Siftable của tôi, nơi bố trí như:

[1 ] [+ ] [2 ]

Đây sẽ là một chuỗi giá trị và tôi sẽ thực hiện các hoạt động cần thiết để đi đến "3".

Tuy nhiên, nếu đứa trẻ là để kéo một vài khối hoạt động cùng nhau như:

[2 ] [\ ] [\ ] [5 ]

Nó sẽ rõ ràng là không hợp lệ.

Cuối cùng, tôi muốn có thể phân tích cú pháp và diễn giải bất kỳ số lượng chuỗi hoạt động nào với các khối mà người dùng có thể kéo cùng nhau. Bất cứ ai có thể giải thích cho tôi hoặc chỉ cho tôi các nguồn lực để phân tích các biểu thức toán học cơ bản?

Tôi muốn câu trả lời độc lập về ngôn ngữ càng nhiều càng tốt.

Answer 1

Bạn có thể xem Shunting Yard Algorithm. Trang wikipedia được liên kết có rất nhiều thông tin và liên kết đến các ví dụ khác nhau của thuật toán.

Về cơ bản, được đưa ra một biểu thức trong ký hiệu toán học infix, nó trả lại một ký hiệu AST hoặc Reverse Ba Lan, bất kể sở thích của bạn có thể là gì.

Điều này page là khá tốt. Ngoài ra còn có một câu hỏi couplerelated về SO.

Answer 2

Trong nhiều ngôn ngữ hiện đại, có các phương pháp để đánh giá biểu thức chuỗi số học. Ví dụ: trong Python

>>> a = '1+3*3'  
>>> eval(a)   
10  

Bạn có thể sử dụng xử lý ngoại lệ để nắm bắt cú pháp không hợp lệ.

Hoặc bạn có thể xây dựng cây biểu thức số học, có một số ví dụ về các đây trong SO: Expression Trees for Dummies.

Answer 3

Như đã chỉ ra ở trên, tôi muốn chuyển đổi chuỗi bình thường (ký hiệu ghi vào) để một biểu thức bài sửa chữa.

Sau đó, với biểu thức sau sửa lỗi, thật dễ dàng để phân tích cú pháp và đánh giá biểu thức. Ví dụ, thêm các toán hạng vào một ngăn xếp và khi bạn tìm thấy một toán tử, các giá trị pop ngoài ngăn xếp và áp dụng toán tử cho các toán hạng. Nếu mã của bạn để chuyển đổi nó thành một biểu thức sửa bài viết là chính xác, bạn không cần phải lo lắng về thứ tự của các hoạt động hoặc bất cứ điều gì như thế.

Phần lớn công việc trong trường hợp này có thể sẽ được thực hiện trong quá trình chuyển đổi. bạn có thể lưu trữ các hình thức chuyển đổi trong một danh sách hoặc mảng để dễ dàng truy cập, do đó bạn không thực sự cần phải phân tích cú pháp mỗi giá trị một lần nữa quá.

Answer 4

Bạn nói rằng một vài toán tử liên tiếp không hợp lệ. Nhưng hãy suy nghĩ về:

5 + -2 

Đó là hoàn toàn hợp lệ.

Biểu thức ngữ pháp cơ bản nhất là như sau:

Expression = Term | Expression, AddOp, Term 
Term  = Factor | Term, MulOp, Factor 
Factor  = Number | SignOp, Factor | '(', Expression, ')' 

AddOp  = '+' | '-' 
MulOp  = '*' | '/' 
SignOp  = '+' | '-' 

Number  = Digit | Number, Digit 
Digit  = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 

Tôi đã từng viết một đơn giản nhẹ biểu hiện phân tích cú pháp/đánh giá (string trong số ra) mà có thể xử lý các biến và chức năng. Mã này là trong Delphi nhưng nó không phải là khó để dịch. Nếu bạn quan tâm tôi có thể đặt mã nguồn trực tuyến.

Answer 5

Lưu ý khác là có nhiều thư viện phân tích cú pháp có sẵn mà một người có thể sử dụng để thực hiện tác vụ này. Nó không phải là tầm thường để viết một phân tích cú pháp biểu hiện tốt từ đầu, vì vậy tôi sẽ khuyên bạn nên kiểm tra một thư viện.

Tôi làm việc cho Hệ thống Singular chuyên về các thành phần toán học. Chúng tôi cung cấp hai trình phân tích cú pháp toán học Jep Java và Jep.Net có thể giúp bạn giải quyết vấn đề của mình. Chúc may mắn!

Answer 6

Đối với đối tượng này, bạn muốn cung cấp phản hồi lỗi khá khác với các lập trình viên được sử dụng cho các thư như "Lỗi cú pháp: không mong muốn '/' ở vị trí foo". Tôi cố gắng để làm một cái gì đó tốt hơn cho giáo dục applet đây:

http://github.com/darius/expr

Những ý tưởng chính: đi đến độ dài bất thường để tìm một chỉnh sửa tối thiểu khôi phục parsability (thực tế kể từ khi biểu thức đầu vào không phải là trang dài), và tạo ra một giải thích dài hơn bằng tiếng Anh về những gì mà trình phân tích cú pháp bị mắc kẹt.