Chuyển đổi biểu thức infix (có dấu ngoặc đơn) thành cây nhị phân

Question

Là một phần của phép gán Java, tôi phải lấy biểu thức số học đầu vào và lưu nó trong cây nhị phân.

Tôi đã làm mọi thứ cần thiết cho bài tập ngoại trừ phần tôi đọc trong chuỗi biểu thức và lưu nó vào cây nhị phân.

Tôi đã tạo một lớp có tên là BinaryTree. Trường duy nhất của nó là một treenode gọi là root. Treenode này được định nghĩa là một lớp bên trong trong BinaryTree. Nó có 3 trường, một trường dữ liệu chung và hai con (trái và phải) là kiểu BinaryTree.

Tôi đang gặp một thời gian rất khó xác định một thuật toán cho việc đọc trong một biểu thức như

(5 * (2 + 3)^3)/2

và lưu trữ nó trong một cái cây như này

  /
     ^  2 
    *  3 
    5 + 
    2 3 

Bất kỳ ai có thể trợ giúp thuật toán không?

Answer 1

Hãy xem qua số shunting-yard algorithm. Từ Wikipedia:

Trong khoa học máy tính, thuật toán shunting-yard là một phương pháp phân tích cú pháp biểu thức toán học được chỉ định trong ký hiệu infix. Nó có thể được sử dụng để tạo ra đầu ra trong ký hiệu Reverse Polish (RPN) hoặc như một cây cú pháp trừu tượng (AST). Thuật toán được phát minh bởi Edsger Dijkstra và đặt tên là thuật toán "shunting yard" bởi vì nó hoạt động giống như một sân shunting đường sắt. Dijkstra đầu tiên mô tả thuật toán Shunting Yard Algorithm trong báo cáo Mathematisch Centrum MR 34/61.

Answer 2

Dưới đây là một số C++ code to create a binary expression tree sử dụng hai ngăn xếp, một cho các toán tử và một cho toán hạng. Cuối cùng, chồng toán hạng chứa một phần tử, cây biểu thức nhị phân hoàn chỉnh.