Thuật toán - giải phương trình tuyến tính trong một biến

Question

Đưa ra một biểu thức dưới dạng một chuỗi, giải cho x. Công suất cao nhất của x trong biểu thức sẽ bằng 1. Các toán tử được phép là +, * và -. Đây là tất cả các toán tử nhị phân. Vì vậy, 2x sẽ được viết là 2 * x. Mỗi toán tử sẽ được theo sau bởi một từ hoặc một hằng số.

Ví dụ, hãy xem xét các phương trình sau:

2 * x + 5 (4 * x-7 + (4-2)) = 10 * x-9

Đây là một hoàn toàn hợp lệ phương trình. Biểu thức của biểu mẫu 1 * 2 * 3 không hợp lệ, nhưng 1 * (2 * 3) là hợp lệ.

Với phương trình như vậy, chúng ta cần tìm giải pháp cho x. Nếu phương trình không hợp lệ, chương trình sẽ hiển thị thông báo lỗi.

Ai đó có thể đưa ra bất kỳ ý tưởng nào về cách khắc phục sự cố này không? Điều duy nhất đang đến với tâm trí của tôi bây giờ là Phân tích và Phân tích bằng cách sử dụng Ngữ pháp Ngữ pháp miễn phí. Nhưng tôi có cảm giác có một giải pháp dễ dàng hơn nhiều. Ai đó có thể ném ánh sáng lên nó được không?

Answer 1

(1) Chuyển đổi e1 = e2 thành e = 0 nơi e = e1 - e2.

(2) Chuyển đổi e thành ax + b, đối với một số a và b.

(3) Giải quyết, x = -b/a.

Bước (2) có thể được xử lý một cách đệ quy, như thế này:

F(k)  = 0x + k // For any constant k. 
F(x)  = 1x + 0 
F(p + q) = let a_1x + b_1 = F(p) 
      and a_2x + b_2 = F(q) 
      in (a_1 + a_2)x + (b_1 + b_2) 
    // Similarly for subtraction. 
F(p * q) = let a_1x + b_1 = F(p) 
      and a_2x + b_2 = F(q) // At least one of a_1 and a_2 must be zero. 
      in (a_1*b_2 + a_2*b_1)x + (b_1*b_2)