phương pháp java để phân tích các biểu thức lồng nhau

Question

cho phép nói rằng tôi đã viết hàm để đánh giá một phép toán đơn giản và tôi có một số đầu vào của người dùng trong một chuỗi như: "1 + [2 + [3 + 4]]" Làm cách nào để phân tích các dấu ngoặc vuông này và trích xuất văn bản bên trong nhiều nhất (3 + 4), đánh giá nó, sau đó phân tích các dấu ngoặc ngoài (2 + 7)? Tôi có một sự hiểu biết thô sơ về tìm kiếm và thay thế Regex, nhưng tôi biết họ sẽ không thực hiện đệ quy như thế này. Tôi muốn một số mã java cơ bản để làm điều này, chưa có một jar/API nếu tôi có thể tránh nó.

Answer 1

Cách sạch nhất để hoàn thành mục tiêu của bạn là viết Lexer và trình phân tích cú pháp cho mục đích này. Viết một recursive descent parser không phải là khó để làm từ đầu cho các biểu thức số học.

Có rất nhiều ví dụ về mã trên web. This is an example mà bạn có thể sử dụng để lấy cảm hứng.

Lexer ở đó để chuẩn hóa đầu vào của bạn và để trừu tượng hóa dữ liệu đó thành luồng mã thông báo. Bằng cách này, trình phân tích cú pháp của bạn chỉ cần làm việc trên các thẻ thay vì bổ sung phải đối phó với các vấn đề khoảng trắng và những thứ gây phiền nhiễu khác.

Twoexamples cho các thuật toán cấp cao dựa trên xếp chồng, another example hiển thị phương pháp tiếp cận gốc đệ quy.

Answer 2

Tôi nghĩ rằng regex không phải là một lựa chọn tốt để đạt được chức năng này

Bạn nên chuyển đổi biểu hiện dùng postfix hoặc ký hiệu tiền tố và sau đó xây dựng một cây biểu từ họ. Đây là một cách tiếp cận tiêu chuẩn trong CS (ngôn ngữ không quan trọng ở đây) để giải quyết vấn đề này theo một cách sạch

Answer 3

Đệ quy hoạt động tốt cho những:

int parse(String expression){ 
    //use a regex to find an instance of [ followed by numbers/operators, followed by ] 
    //replace it with parse(whatever's inside the brackets) 
    //continue until there are none left 
    //evaluate the string (which should be a sequence of numbers and operators without brackets) 
} 

Answer 4

Sử dụng một chồng. Khi bạn gặp một khung mở, hãy đẩy bất cứ thứ gì bạn đang làm việc lên ngăn xếp và bắt đầu biểu thức mới. Khi bạn nhấn một khung đóng, hãy bật ngăn xếp và sử dụng biểu thức bạn vừa tính làm mục tiếp theo. Hoặc, như áp phích trước đó đã nói, sử dụng đệ quy hoặc một cây.

Answer 5

Đối với Java, bạn có thể sử dụng JavaCC cho trình phân tích cú pháp/lexer. Tôi đã sử dụng cái này trong nhiều dự án. Nó khá dễ sử dụng. Một trong những ví dụ, tôi nghĩ, bao gồm một phân tích số học. JavaCC sẽ xây dựng cây cú pháp nơi bạn có thể đi qua.

Thử sử dụng số học bằng JavaCC sẽ cung cấp phần giới thiệu tốt cho Ngữ cảnh miễn phí ngữ cảnh và khái niệm về Cây cú pháp trừu tượng. Nếu bạn đang học, thì đó là một bước tốt để thực hiện sau khi thử những gì @emboss đề xuất