问题标签 [infix-notation]

如何扩展中缀和堆栈优先级以包括运算符<, >, <=, >=, ==, !=, !, &&, 和||?

在解析中缀表达式时，例如：P + (Q – F) / Y#，每个符号都有一个与其操作顺序相关的优先级。/并且*具有比+和更高的优先级-。

以下是我拥有/理解的优先事项：

我想为内置类型（例如 Double）添加一个方法，以便我可以使用infix运算符。那可能吗？

我一直在考虑创建一种非常适合创建 DSL 的语言，方法是允许定义中缀、后缀、前缀甚至由多个单词组成的函数。例如，您可以如下定义中缀乘法运算符（其中 multiply(X,Y) 已定义）：

或后缀“平方”运算符：

或者是 C 或 Java 风格的三元运算符，它涉及两个散布在变量中的关键字：

显然，在这种语言中存在很多歧义，但如果它是静态类型的（使用类型推断），则可以消除大多数歧义，并且可以将剩余的歧义视为语法错误（通过添加括号来纠正合适的）。

是否有一些我看不到的原因会使这变得极其困难、不可能，或者只是一个糟糕的主意？

编辑：许多人向我指出了可能执行此操作或类似操作的语言，但我实际上对如何实现我自己的解析器的指针感兴趣，或者如果这样做我可能会遇到的问题。

挑战

这是挑战（我自己的发明，但如果它以前出现在网络上的其他地方，我不会感到惊讶）。

编写一个函数，该函数接受单个参数，该参数是简单数学表达式的字符串表示形式，并将其计算为浮点值。“简单表达式”可以包括以下任何一种：正数或负数十进制数、+、-、*、/、(、、)。表达式使用（正常）中缀表示法。运算符应该按照它们出现的顺序进行评估，即不像在 BODMAS中那样，当然应该正确地观察括号。该函数应该为任何返回正确的结果这种形式的可能表达。但是，该函数不必处理格式错误的表达式（即语法错误的表达式）。

表达式示例：

规则

我预计这里会有某种形式的“作弊”/狡猾，所以请让我提前警告！通过作弊，我指的是eval在动态语言（如 JavaScript 或 PHP）中使用或等效函数，或者同样在运行中编译和执行代码。（我认为我对“无 BODMAS”的规范几乎可以保证这一点。）除此之外，没有任何限制。我预计这里会有一些正则表达式解决方案，但很高兴看到更多。

现在，我主要对这里的 C#/.NET 解决方案感兴趣，但任何其他语言也完全可以接受（特别是用于功能/混合方法的 F# 和 Python）。我还没有决定是否接受最短或最巧妙的解决方案（至少对于语言）作为答案，但我欢迎任何语言的任何形式的解决方案，除了我刚刚在上面禁止的！

我的解决方案

我现在在这里发布了我的 C# 解决方案（403 个字符）。更新： 在一些可爱的正则表达式的帮助下，我的新解决方案在294 chars上明显击败了旧解决方案！我怀疑这很容易被一些语法较轻的语言（特别是功能/动态语言）击败，并且已被证明是正确的，但我很好奇是否有人仍然可以在 C# 中击败它。

更新

我已经看到了一些非常狡猾的解决方案。感谢所有发布过的人。尽管我还没有测试过它们中的任何一个，但我会相信人们并假设他们至少可以使用所有给定的示例。

只是为了说明，重入（即线程安全）不是该功能的要求，尽管它是一个奖励。

格式

为了便于比较，请按以下格式发布所有答案：

语言

字符数：???

完全混淆的功能：

清除/半混淆功能：

关于它所采用的算法/聪明快捷方式的任何注释。

假设用户输入一个中缀表达式作为字符串？使用 C 语言评估该表达式的结果可能是最简单的（最简单的意思是shortes t）方法？

可能的方法是将其转换为后缀，然后使用堆栈。但这是一个相当长的过程。是否有任何方法可以使用诸如atoi()或eval()之类的函数来简化工作？

是否可以使用管道中缀运算符在返回的对象上调用方法？

例如，我有一个带有方法 (Method1) 的 .Net 类 (Class1)。我目前可以这样编码：

我知道我也可以这样编码

但是我希望能够将它流水线化（我正在使用 ? 下面我不知道该怎么做）：

此外，假设我有一个返回对象的方法，并且我只想在该方法没有返回 null 时引用它（否则保释？）

或者为了更清楚，这里有一些 C# 代码：

我的解析器通过首先从中缀转换为后缀然后使用标准后缀评估规则来评估 PEMDAS 表达式。我解析表达式并将标记存储在列表中。这个预编译对我来说没问题，因为我计划缓存预编译的函数。

我正在尝试优化评估函数（参见代码中的 Evaluate04）。在我的硬件上，我可以在不到 600 毫秒的时间内完成 1,000,000 次评估。老实说，我相信这已经足够快了。比数据库访问调用获取表达式要快得多。

我想看看你们能不能让它更快。微优化，类的完整重构。它是如何完成的并不重要。

这是我能得到的最快的，你能改进它吗？

我的任务是编写一个应用程序（不幸的是在 C 上），它以中缀表示法（使用变量、一元和二元运算符）读取表达式并将其存储在内存中，然后对其进行评估。此外，还应检查正确性。

例如：

3*(A+B)-(-2-78)*2+(0*A)

在我得到所有值之后，程序应该计算它。

问题是：最好的方法是什么？（优化和验证）

选择什么符号作为树的基础？

我应该将表达式表示为树吗？如果是这样，我可以轻松地对其进行优化（只需删除返回 0 或其他的节点）。

干杯，

我正在尝试在 C++ 中实现前缀到中缀，这就是我到目前为止所得到的。例如，输入应该是这样的：

和输出：

但相反，我得到：

这是我到目前为止写的代码：

我想在 C++ 中评估一个表达式。为了评估它，我希望将表达式转换为前缀格式。

这是一个例子

以下是可能的方法。

这里And , Or , Not是保留字，括号 (" ( ", ) ) 用于范围

Not具有更高的优先级

并将下一个优先级设置为 Not

Or设置为 And 的下一个优先级

空白用于分隔符。表达式没有其他元素，如TAB，NEWLINE

我不需要算术表达式。我可以进行评估，但有人可以帮我将字符串转换为前缀表示法吗？