你可以使用正则表达式来实现分流算法吗？

Question

你可以用正则表达式来实现shunting yard algorithm吗？

Answer 1

我相信这已经在这里找到答案：Can the shunting yard algorithm parse POSIX regular expressions?

我会说，回答你的问题是“没有，你可以使用正则表达式不 实现调度场算法。” 这与您使用 正则表达式无法解析任意HTML的原因相同。归结为：

正则表达式没有堆栈。由于分流场 算法依赖于堆栈（在将中间转换为RPN时将推进和弹出操作数），则正则表达式不具有执行此任务的计算“能力”。

这掩盖了很多细节，而是一个“正则表达式”是一种方式 定义正规语言。当你“使用”正则表达式，你 问电脑说：“看文本的身体，告诉我 任何这些字符串的是否是我的语言，我使用的是常规定义的语言 表达。”我将通过常规语言指向this most excellent answer which you and everyone reading this should upvote 了解更多信息。

所以，现在你需要一些数学概念，以创造更强大的语言，以增加“定期 语言”。如果您将 描述为分流码算法作为计算能力模型 的实现，那么您可能会说该算法将是 ，如context-free grammar（嗨，您知道什么， 链接使用表达式分析树作为例子。）A push-down automata。与堆栈的东西。

如果您不熟悉自动机理论和复杂性 类，那么这些维基百科文章可能没有帮助 而没有从头开始解释它们。

问题的关键是，你可以使用正则表达式来帮忙写分流 院子。但是，正则表达式在执行具有 任意深度的操作时并不是很好，这个问题就是这样。所以我不会花太多时间去解决这个问题的正则表达式。

Answer 2

我不这么认为。正则表达式只能匹配常规语言（请参阅Regular language），而中缀表达式则是一种上下文无关语言（请参阅Context-free language）。例如，您无法将正确匹配的括号与正则表达式匹配。