logo标签列表

数学表达式的解析

calgorithmparsingdata-structures
10
(in c90) (linux)
input:
sqrt(2 - sin(3*A/B)^2.5) + 0.5*(C*~(D) + 3.11 +B)
a
b   /*there are values for a,b,c,d */
c
d

输入：

cos(2 - asin(3*A/B)^2.5) +cos(0.5*(C*~(D)) + 3.11 +B)
a
b   /*there are values for a,b,c,d */
c
d

输入：

sqrt(2 - sin(3*A/B)^2.5)/(0.5*(C*~(D)) + sin(3.11) +ln(B))
 /*max lenght of formula is 250 characters*/
a
b   /*there are values for a,b,c,d */
c   /*each variable with set of floating numbers*/
d

如您所见，输入中的中缀公式取决于用户。我的程序将接受一个公式和n个元组值，并计算每个a、b、c和d值的结果。如果您想知道，程序的结果是图形。

有时候，我觉得将输入存储在字符串中，然后另一个想法浮现出来："我应该将公式存储在结构体中"，但我不知道如何基于结构体构建代码。

实际上，我不知道如何在程序代码中存储公式以便我能完成我的工作。你能给我展示一下吗？

/* a,b,c,d is letters
 cos,sin,sqrt,ln is function*/
8
你真的需要更好地解释一下自己。 - Tomer Vromen
@Matsemann 是的，当您重新标记问题时，这是预期的行为。无论帖子有多老，错误的标签都是错误的标签。 - Gilles 'SO- stop being evil'
5个回答
13
你需要编写一个词法分析器来对输入进行标记化（将其分解为其组成部分--运算符、标点符号、标识符等）。最终，你会得到一些令牌序列。
之后，有许多方法可以评估输入。其中一种最简单的方法是使用Shunting Yard算法将表达式转换为后缀表达式（使用后缀表达式进行评估非常容易）。
2
您应该查找“抽象语法树”和“表达式树”，以及“词法分析”、“语法”、“解析”和“编译器理论”。对于大多数事物来说，从文本输入中获取意义是相当困难的（尽管我们通常会尝试确保我们有简单的输入）。
生成解析器的第一步是编写输入语言的语法。在这种情况下，您的输入语言是一些数学表达式，因此您可以做如下操作：
expr => <function_identifier> ( stmt )
        ( stmt )
        <variable_identifier>
        <numerical_constant>

stmt => expr <operator> stmt

我已经好几年没有写过像这样的语法了（请查阅BNF和EBNF），所以我可能会犯一些明显的错误，但会有其他人友善地指出。

根据你如何处理运算符优先级（乘除比加减等），这可能会变得更加复杂，但是在这种情况下语法的目的是帮助你编写解析器。

有一些工具可以帮助你完成这项任务（如yacc、bison、antlr等），但你也可以手动完成。有许多方法可以做到这一点，但它们都有一个共同点——堆栈。处理这种语言需要使用一种称为下推自动机的东西，它只是一种可以基于新输入、当前状态和堆栈顶部项进行决策的方式。它可以做出的决策包括压入、弹出、改变状态和组合（将2+3转换为5就是一种组合形式）。组合通常被称为产生式，因为它产生了一个结果。

在各种常见的解析器类型中，你几乎肯定会从递归下降解析器开始。它们通常直接用通用编程语言（如C）编写。这种解析器由多个（通常很多）函数组成，它们互相调用，并最终使用系统堆栈作为下推自动机堆栈。

你还需要写下构成你的语言的不同类型的单词和运算符。这些单词和运算符称为词素，代表你的语言的标记。我在语法中用<like_this>表示这些标记，括号除外，它们表示它们自己。

你最有可能想用一组正则表达式来描述你的词素。如果你使用过grep、sed、awk或perl，你应该熟悉它们。它们是一种描述所谓的正则语言的方式，可以被一些称为有限状态自动机的东西处理。这只是一种说法，即它是一个程序，可以通过仅考虑其当前状态和下一个输入（下一个字符的输入）来做出关于改变状态的决策。例如，你的词法描述的一部分可能是：

[A-Z]   variable-identifier
sqrt    function-identifier
log     function-identifier
[0-9]+  unsigned-literal
+       operator
-       operator

还有一些工具可以为此生成代码。其中之一是高度与解析器生成程序yacc集成的词法分析器lex，但由于您正在学习，因此您也可以使用C编写自己的标记化/词法分析代码。

在完成所有这些工作之后（可能需要相当长的时间），您需要让解析器构建一个树来表示输入的表达式和语法。在表达式求值的简单情况下（例如编写一个简单的命令行计算器程序），您可以让解析器在处理输入时评估公式，但对于您的情况，我理解的是，您需要制作一棵树（或逆波兰表示法，但在我看来，树更容易）。

然后，在读取变量的值之后，您可以遍历树并计算实际数字。

2
可能最简单的方法是使用Lua或Python这样的嵌入式语言，它们的解释器都是用C编写的。不幸的是，如果你选择Lua，你将不得不将二进制操作转换为函数调用，在这种情况下，使用Python可能更容易。所以我会选择Python。
如果你只想将结果输出到控制台，那么这真的很容易，你甚至不需要深入了解Python嵌入。因此，你只需要在Python中编写一行程序来输出值。
以下是你可以使用的Python代码：
exec "import math;A=<vala>;B=<valb>;C=<valc>;D=<vald>;print <formula>".replace("^", "**").replace("log","math.log").replace("ln", "math.log").replace("sin","math.sin").replace("sqrt", "math.sqrt").replace("cos","math.cos")

请注意，替换操作是在Python中完成的，因为我相信在Python中执行此操作比在C中更容易。另外请注意，如果您想使用xor('^')，则必须删除.replace("^","**")并使用**进行幂运算。
我不知道足够的C语言来告诉您如何在C中生成此字符串，但是在生成后，您可以使用以下程序来运行它：
#include <Python.h>

int main(int argc, char* argv[])
{
  char* progstr = "...";
  Py_Initialize();
  PyRun_SimpleString(progstr);
  Py_Finalize();
  return 0;
}

您可以在此处查找有关在C中嵌入Python的更多信息：Python扩展和嵌入文档

如果需要在程序中使用计算结果，则有方法从Python中读取该值，但您需要自行了解这些方法。

嘿。我认为这是作弊；-）。用Python实现这个比用C实现更容易，但在C中实现表达式求值器既有趣又有趣（好吧，它可能会有趣；我从未在C中实现过一个，但我在C++中实现过一个，600行代码后，我对如何评估表达式有了更多的了解 :-)）。 - James McNellis
如果目标是学习表达式求值，我同意；否则，如果这只是一个中间步骤，那么这样做既更容易也更少出错。你可以将其与使用标准库功能进行比较。当被要求编写自己的代码时，使用它是作弊的；否则，这样做是有道理的。:) 但是，是的，我同意这可能是一个有趣的学习经历，我还没有尝试过。 - JPvdMerwe
一个有效的观点：由于原帖没有说明他的目的是什么，这个解决方案是一个好主意（+1）。 - James McNellis
0
此外，您应该查看有关二叉树的SO帖子和其他帖子。使用树结构实现此功能。遍历作为中缀以进行评估。对于树问题已经有一些很好的答案。
如果您需要存储此内容（例如在文件中进行持久化），我建议使用XML。解析XML应该让您真正欣赏到您的任务有多容易。
-1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接