设计符号方程求解器

Question

在一堂课上，我被分配到一个项目来完成基本方程求解器。它需要求解线性方程。例如。我应该能够解出一些方程：

• a*x + b = c
• ax + b = cx + d
• 16*x – 9*x = a
• x/16 – x/9 = a
• 8*(x+3) – 5*(x+4) = 12
• x^2 + 2*x + 1 = 0
• (x + 1)*(x – 1) = 0
• (x + 1)(x – 1) = 2(x-1)
• x – 2*sqrt(x) + 1 = 0
• log 3*x - log 6 = 1
• log 3*x – log 6*x^2 = a
• 2^(x-1) * a = 2^(3*x+1)

我看过了，只发现了一些有用的建议。我试图理解这个实现，但没能看到我把算术规则放在哪里。我尝试阅读 Sympy 源代码，但我不知道要查找我要查找的内容。我想在txt文件中定义某些规则。例如 u - v + v = u 并尝试了解如何将此规则应用于方程。

你们中有人知道我该如何设计这个吗？

Answer 1

首先，您应该考虑如何为此目的声明方程（或多项式）。例如，您可以定义

data Polynomial = Polynomial [Polynomial]
   | Sum Polynomial Polynomial
   | Ln Polynomial
   | Log10 Polynomial Polynomial
   | Var String -- a named Variable
   | ...

为了轻松处理多项式，您可以为 Eq、Ord、Num 等数据类型多项式创建实例，这样您就可以像处理数字一样处理多项式。

instance Num Polynomial where
    a + b = ...

要创建这些函数，您可以轻松使用模式匹配：

(Sum a b) + (Sum c d) = Sum (Sum a b) (Sum c d)

对于方程，您可以简单地使用元组并为其创建一个新类型：

type Equation = (Polynomial, Polynomial)

为了解决这个问题，可以使用这样的函数：

solve :: Equation -> String -> Polynomial

...其中字符串是变量的名称。

解决问题不需要做真正的工作。同样，对于这个模式匹配可以用于第一步：

solve ((Sum (Var a) b, e) x -- solves polynomials of type a + b = c + d
    | a == x = Sum e (negate b)
    | ...

当然，这是非常基本的，您可以做得更聪明，通过使用标准化来减少可能的情况数量，例如将“a + a + a”合并为“3 * a”。

Answer 2

您可以选择编写自己的数学表达式解析器/解释器或使用现有的。 Jep 是开源数学表达式解析器的一个很好的例子。

否则，如果您想了解编译器和语法分析器在幕后的作用，那么您可以使用 jFlex 和 CUP

编写自己的表达式解析器

此外，这里是关于 antlr 的优秀教程，可能会帮助您入门。

Answer 3

其实没什么特别的。你只是孤立了x。无需外部工具，只需几行即可完成。

class Node:
    def __init__(self, type, val, left=None, right=None):
        self.type, self.val, self.left, self.right = type, val, left, right
    def __repr__(self):
        return f'({self.left!r} {self.val} {self.right!r})' if self.type == 'op' else str(self.val)
    def __str__(self, lp=0, rp=0, op=''):
        if self.type != 'op':
            return str(self.val)
        p = 1 + '+-*/'.find(self.val)//2
        l, r = self.left.__str__(p, 0, self.val), self.right.__str__(0, p, self.val)
        return ('(%s)' if (p<rp or (p==rp and op in '-/') if rp else p<lp) else '%s') % f'{l} {self.val} {r}'

def parse(s):
    def parse_expr(min_p = 0):
        x = q.pop()
        node = (parse_expr(), q.pop())[0] if x=='(' else Node('number' if x.isdigit() else 'var', x)
        while q and (p := 1 + '+-*/'.find(q[-1]) // 2) > min_p:
            node = Node('op', q.pop(), node, parse_expr(p))
        return node
    q = s.replace(')', ' )').replace('(', '( ').split()[::-1]
    return parse_expr()

def solve(s):
    a, b = s.split(' = ')
    l, r = map(parse, (a, b) if 'x' in a else (b, a))
    while l.type=='op':
        op = '-+/*'['+-*/'.find(l.val)]
        if 'x' in str(l.left):
            l, r = l.left, Node('op', op, r, l.right)
        else:
            l, r = l.right, Node('op', op, r, l.left) if l.val in '+*' else Node('op', l.val, l.left, r)
    return f'{l!r} = {r!r}'