将字符串转换为C语言中的计算结果

3
我想知道是否有人了解如何实现一个看似简单但在编程时并不简单的功能。 这个想法是:给出一个包含方程式的字符串,例如:"2*x = 10"(这很简单,但它可能会变得非常复杂,例如sqrt(54)*35=x^2;等等...),程序将返回x=5,并可能给出计算过程的日志。
这可行吗?如果可以,有人有线索吗?值得一提的是,有这个网站(http://www.numberempire.com/equationsolver.php)可以在PHP中完成相同的操作,但它不是开源的。
感谢任何帮助!

这对于像 2x = 10 这样的简单内容来说很容易,但对于其他所有内容,我想它可能会变得非常复杂。最难的部分实际上是解决方程,而不是解析它。 - IVlad
你需要这个做什么?如果你必须问如何做到这一点,那么很可能你不会接近像Mathematica这样的程序已经在多年的过程中完成的内容。在我看来,与这样一个程序进行接口操作比重新发明一个非常复杂的轮子要容易得多。 - IVlad
1
@Alexandre:原因在于物理和工程中的所有实际问题都无法通过解析方法求解。相反,通常使用数值方法来找到近似解,通常是通过重复线性化来实现的。例如,可以查看PetsC或Eigen等先进的免费软件示例,以用于解决这些问题。 - user168715
你好,Alexandre。你最终找到解决这种简单方程的方法了吗?我正在尝试在C#中做同样的事情。最好的问候。 - bobby
我负责主导。请查看我的答案。我们使用RRT算法和多项式分解来实现求解。 - Sergei Krivonos
显示剩余5条评论
7个回答

3
这被称为“解析”,虽然计算机科学已经解决了这个问题,但在您完全理解它之前,它并不简单。有一个完整的计算机科学学科来描述如何解决这个问题。在C语言中,您必须定义输入的语法(可能带有优先级规则),然后对输入执行“词法分析”,然后对结果进行“解析”,最后评估您的解析树。
而在像Ruby这样的语言中,由于您具有如此全面的字符串操作支持以及如此巨大的运行时能力,因此您可以使用一行代码解决您的问题,如下所示:
puts(eval($_)) while gets

是的,这将涵盖比你要求的更多内容。

“eval()” 命令是如何起作用的?它是否评估给定字符串中的每个字符? - Alexandre Cassagne
eval() 函数接受一个字符串作为参数,并将其评估为该语言中的脚本。这个函数在几乎所有解释型语言中都非常常见——任何不使用编译器来执行其代码的语言。Perl、Python、Bash 等都有 eval() 函数或内置函数。 - wilhelmtell
因为每个 Ruby 表达式都会评估出一个值,所以 eval() 函数总是有一个返回值。因此,上面的代码只是将 eval() 返回的内容打印到屏幕上。eval() 的参数是最后一个表达式的值,在这种情况下是 gets() 调用。gets() 从标准输入中获取一行并返回它。如果它获取到文件结束符,则其布尔值为 false。 - wilhelmtell
简单来说,eval() 函数解释和评估 Ruby 代码,任何 Ruby 代码。因为 4+5 实际上是 Ruby 代码(它的值为 Fixnum9),所以 eval() 函数接受它并将其解析为这样的代码。它将解释任何 Ruby 代码:如果您键入 4+5,则会得到 9,如果您在输入框上方键入“计算器”代码 File.open("there","w") {|f| f.puts("be dragons")},那么脚本将愉快地创建一个文件并写入它。确实是一个强大的计算器,也许太强大了。它可以计算任何东西,毫无疑问。 - wilhelmtell
很好,我现在要试试将一个 Ruby 文档链接到 C 语言 谢谢 :) - Alexandre Cassagne
@wilhelmtell - 你之前三个评论中包含的内容的摘要将是你答案的有价值补充。 - ryyker

2

首先您需要正确定义可以作为输入的方程种类,然后应该创建一个好的抽象来表示方程,例如多项式类。当您想要使用更复杂的表达式时,可以使用数值表达式树。如果您有好的规则将表达式转换为前缀记法,那么解析可能会很容易,然后使用堆栈轻松进行评估。一旦您拥有算术树或多项式,就可以实现变量计算的转换。


就我而言,解析非常复杂,我们要讨论的是获取一个字符串,它可以期望任何值,它既可以是“x3+5=12”,也可以是“x+1=1”或“x2*3.14159”或其他任何内容,方程式没有具体规则,除了“左成员使用符号'='与右成员分开”。这使得方程式的解析非常复杂。 - Alexandre Cassagne
@Alexandre Cassagne 给您举个算术树的例子,例如 "x3+5=12",首先您要搜索最重要的 "=" 并把它作为根。然后递归地查找左边("x3+5")和右边("12")的最重要的操作符。对于左边部分,没有 "=",但有"+",因此左子节点是加法操作,现在再递归处理左边部分("x*3")... 您树的叶子将是常量或变量。 - Gabriel Ščerbák
@Alexandre Cassagne 解决这个方程就像在树中找到变量叶子,逐步从“=”根节点到叶子节点的路径上删除节点,通过将操作转换为其对应项(加号变减号...),并将其添加为“=”的另一个子节点。最后,“x”将成为“=”的子节点,评估“=”的另一个子节点将给出结果。评估是简单的中序遍历。 - Gabriel Ščerbák
@Alexandre Cassagne,如果您正在询问此解决方案的设计,请使用组合设计模式来设计算术树,并使用访问者设计模式进行评估,使用迭代器设计模式遍历树。 - Gabriel Ščerbák
非常感谢 :) 我要开始尝试了 :P 我会尝试将我的代码公开,因为在我看来,方程应该是公共领域 ^^ - Alexandre Cassagne
显示剩余2条评论

1
通常情况下,您需要将表达式解析为某种内部表示形式。许多线性代数书籍建议使用矩阵(或std::vector)来表示系数。项的指数由其在向量中的位置定义。
例如,对于以下表达式:
 2 + 3x + 5x^2

可以表示为数组或std::vector

std::vector<int> expression;
expression[0] = 2; // 2 * x ^ 0
expression[1] = 3;
expression[2] = 5;

编写评估函数变得微不足道,留给读者作为练习。

解决多个方程变得更加复杂。已经存在用于此的库和算法。通过谷歌搜索应该能找到好的东西。 :-)

我建议从简单术语开始,并构建一个解析器。一旦这样做成功,您可以更改解析器以接受函数名称。

如果您正在尝试简化在等号两侧都有项的表达式,请写下手动求解时通常要采取的步骤。尝试一些不同的方程以制定一些规则。现在在C++中实现这些规则。


实际上,谷歌搜索并没有出现很多有趣的东西,但我会尝试一些方法在页面上继续搜索。谢谢 :) - Alexandre Cassagne

1
如果方程变得复杂,那么用几行C/C++代码肯定是不够的。
对于线性方程,你需要模拟线性代数书中描述的方法之一。这段代码足够小。

首先,正如我在评论中多次提到的那样,解析是第一步,然后方程必须以抽象的方式“描述”,也就是在一个类中,最后才能得到解决... 我不认为这可以用几行代码来实现... 哈哈,无论如何还是谢谢。附言:你所说的书名是什么? - Alexandre Cassagne
我没有谈论任何特定的书,但你可以查看《初等线性代数》Howard Anton。你可以尝试谷歌搜索“高斯消元”。 - Shamim Hafiz - MSFT

1

一个更正:这不是线性代数,通常意味着多个方程和未知数的矩阵。

你的例子肯定不复杂。

你需要的是一个简单的表达式语法和解析器。将方程解析成抽象语法树并遍历该树以进行评估。

如果你正在编写Java,它可能看起来像this。另一个例子是symja。也许这足以激发你自己为C++设计的灵感。

你还可以查看Mathematica和Wolfram's Alpha。Stephen Wolfram是世界上最好的数学家和计算机科学家之一。他有很多东西可以让你重复使用,而不是自己编写。

你必须定义你所说的“解决”是什么,以及你希望得到什么返回。

有符号解和数值解。你指的是哪一个?两者都同样有效,但它们是不同的。根据你的答案,你将应用不同的技术。

另外一点:解方程有很多技巧,这些技巧很大程度上取决于方程的类型。如果你给我一个像f(x)=0这样的方程,我会想到使用牛顿迭代法之类的根查找算法来解决它。如果你给我一个普通微分方程,我可能会尝试代换法或者使用龙格-库塔数值积分。如果你给我一个偏微分方程,我可以应用有限差分、有限元或边界元技术。(别让我开始讲椭圆型、抛物型和双曲型偏微分方程了。)
问题在于你的问题非常泛化,答案很大程度上取决于你要做什么。更多的细节可能会有所帮助。

这还不够,因为他不仅仅对评估数学表达式感兴趣,而是对解方程感兴趣。他还需要一种能够解决任何方程的方法。 - IVlad
实际上,这个项目分为两部分: 第一部分是创建一个方程类型/对象,它能够解析任何字符串(例如我展示的网站http://www.numberempire.com/equationsolver.php),这可能是最难的部分,因为它必须接受任何输入,如x=3/2和x^2=(x+2)*4+7^2(这只是一个随机示例,但它解析字符串的事实使它很难,因为它需要预期任何内容)。 此外,第二部分——解决方程——应该会更容易,尽管我不确定它是否确切地是“两行代码”,但我希望能找到方法…… - Alexandre Cassagne

1
你可以尝试将SymPy链接到你的C(或C++)代码中,并使用它来解决你的方程。
如果我没记错,SymPy有这种功能。此外,在Python内部操作输入字符串以获得可用的方程式应该更容易,然后将其传递给SymPy进行求解。

1
你的问题将分为两个部分:解析方程和符号求解。我不会在第一个方面多说什么,因为其他答案已经很好地涵盖了这个主题;我的个人建议是编写一个简单的前缀表达式递归下降解析器。
第二部分,解析地解决方程,将会很棘手。一般来说,有特殊类别的方程可以使用标准方法找到解析解:
  • 线性方程组:任何直接的线性求解器。如果您想明确显示步骤并且方程/未知数的数量很少,我建议使用像未选定的高斯消元或克莱默法则之类的简单方法。
  • 多项式方程组:等效于变量替换后找到单个多项式的根。如果它们的次数<=4,则有精确解的公式。注意:对于3次和4次,这些公式并不愉快。
  • 具有有理系数的多项式方程组的有理解:像上面那样进行变量替换。然后使用有理零测试进行暴力破解。
  • 其他类型的方程:祝你好运。对于更复杂的[系统]非线性方程,如果您可以接受数值(非解析)解,可以研究牛顿法。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接