问题标签 [shunting-yard]

I'm looking to implement the Shunting-yard Algorithm, but I need some help figuring out what the best way to split up a string into its tokens is.

If you notice, the first step of the algorithm is "read a token." This isn't exactly a non-trivial thing to do. Tokens can consist of numbers, operators and parens.

If you are doing something like:

(5+1)

A simple string.split() will give me an array of the tokens { "(", "5", "+", "1", ")" }.

However, it becomes more complicated if you have numbers with multiple digits such as:

((2048*124) + 42)

Now a naive string.split() won't do the trick. The multi-digit numbers are a problem.

I know I could write a lexer, but is there a way to do this without writing a full-blown lexer?

I'm implementing this in JavaScript and I'd like to avoid having to go down the lexer-path if possible. I'll be using the "*", "+", "-" and "/" operators, along with integers.

我一直致力于在 JavaScript 中为类实现 Shutting-Yard 算法。

这是我到目前为止的工作：

到目前为止它工作正常。如果我给它：

((5+3) * 8)

它将输出：

中缀：((5+3) * 8)
后缀 (RPN)：5 3 + 8 *
结果：64

但是，我正在努力实现一元运算符，因此我可以执行以下操作：

(( -5 +3) * 8)

实现一元运算符（否定等）的最佳方法是什么？另外，是否有人对处理浮点数有任何建议？

最后一件事，如果有人看到我在 JavaScript 中做任何奇怪的事情，请告诉我。这是我的第一个 JavaScript 程序，我还不习惯。

出于学术目的，我必须编写一个绘制用户输入表达式的应用程序，例如： f(x) = 1 - exp(3^(5*ln(cosx)) + x)

我选择编写解析器的方法是使用 Shunting-Yard 算法转换 RPN 中的表达式，将像“cos”这样的原始函数视为一元运算符。这意味着上面编写的函数将转换为一系列标记，例如：

问题是要绘制函数，我必须多次评估它，因此对每个输入值应用堆栈评估算法效率非常低。我该如何解决这个问题？我必须忘记 RPN 的想法吗？

问题是：假设我有一个sin(2-cos(3*A/B)^2.5)+0.756*(C*D+3-B)使用 BNF 指定的输入函数，我将使用递归下降算法解析输入，然后如何使用或更改 Dijkstra 的算法来处理这个给定的函数？我需要用罪来执行它 | COS | 平方 | ln，Dijkstra 的算法应该在其中完成工作。

编辑：也许我还应该问：表示给定功能的最佳实践或数据结构是什么？

编辑：输入集可以获取为：

编辑：Shunting Yard 是将输入函数转换为 RPN 的算法，但是如何扩展它以接受另一个函数，如 sin | COS | 平方 | 吗？递归下降是否为调车场提供了所需的扩展？

我正在实施调车场算法。我无法检测何时缺少运算符的参数。维基百科条目在这个主题上非常糟糕，并且他们的代码在下面的示例中也崩溃了。

例如3 - (5 + )不正确，因为+缺少参数。

就在算法到达 之前)，运算符堆栈包含- ( +并且操作数堆栈包含3 5。然后它是这样的：

• +它从运算符堆栈中弹出
• 发现这+是一个二元运算符
• 弹出两个操作数，应用运算符并将结果 ( ) 推8送到操作数堆栈
• 然后它(从堆栈中弹出匹配项，并继续

那么我怎样才能检测到+缺少参数呢？如果您还更新了维基百科，那就再好不过了 :-)

我正在尝试制作从后缀到中缀符号的转换器，需要一些帮助。已经有一个关于中缀到后缀转换的问题，它给出了一个我无法转换回来的例子。（注意：那里缺少减号！）

以下是我的转换器的输出，其中第一个“列”是后缀输入，第二个是我的中缀输出，第三个是我可能应该得到的（？）：

你认为有可能解决这个问题，还是最后两行实际上转换正确？你会如何编写算法来解决这个问题？

请假设更多的运算符（不仅是+and -）可以设置为一元和二元，其中一元运算符的优先级高于二元运算符。

参考

1. Ruby Quiz #148: Postfix to Infix，同样来自Google Groups
2. 在 LiteratePrograms 上具有一元运算符支持的调车场算法（C、Python、Perl）

我正在测试一个中缀到后缀到中缀的转换器，并发现了某种不确定性。例如，一个简单的中缀和

可以转换为后缀一

假设不累积具有相同优先级的运算符。如果他们是那么我得到

另一方面，以下所有后缀表达式都可以转换为初始和

所有这些后缀表达式都正确吗？

更新1

如果你要做这样的转换器，你会选择哪种形式？我需要选择一个进行测试。

我正在寻找可以解释 php 中的字符串并执行简单的数学计算的东西，然后返回一个关于表达式是真还是假的布尔结果。

例如：

1. 苏类型在“3*{mysalary}/9=10000”
2. PHP 将其拆分为两个表达式 - explode('=',string);
3. PHP 获取我的数据库字段列表，并用数据替换任何“{}”分隔的字段（类型转换为 int）
4. 然后 PHP 计算数学表达式
5. php 然后将左侧与右侧进行比较
6. 产生的布尔结果。

它可能听起来很复杂，但它只需要非常简单。以下是约束： 1/ 数学运算符固定为：+ - / * 2/ 比较运算符固定为： = > < >= <= 3/ 不需要浮点比较，一切都可以在整数级别完成。因此，如果需要，可以对任何除法进行四舍五入，或者只是对最终结果进行四舍五入

永远只有两个表达式，一个比较运算符。如果有任何类型的错误，我们将返回 false。

有没有人见过可以做到这一点的东西？我知道我可以做点什么，但为什么要重新发明轮子呢？

如果您还没有看到任何东西，您是否愿意列出一些您在构建它时可以想到的“陷阱”或警告。

在阅读了更多内容后，我意识到我可以使用调车场算法。有没有人在 PHP 中实现了这个？

我知道 eval 可能是执行此操作的一种简单方法，但是，我担心用户可能很容易使用此方法破坏某些内容或导致语法错误。我宁愿不将它包含在解决方案中，或者如果我这样做了，那么它需要严格控制它的使用方式。

谢谢。

杰森

我正在尝试使用 Shutting Yard (SY) 算法解析语法。语法包括以下命令（不过还有很多其他命令！）

本质上， setxy 是一个函数，但它不需要任何函数参数分隔符。由于缺少括号和函数参数分隔符，这使得通过 SY 进行操作变得非常困难（不可能？）。

知道 SY 是否可用于解析无括号/函数参数无分隔符的函数，还是应该继续使用不同的解析算法？如果是这样，你会推荐哪一个？

谢谢！DJ22

我正在努力在 Common Lisp 中自己写一些东西，实现 Shutting-yard 算法。我认为它没问题，即使它看起来相当丑陋并且如果我怀疑它的 Lispy 特性，但是在测试 REPL 中的函数时，我得到了标题中的错误。

代码如下，测试用例为(shunting-yard '(3 + 5)).

是代码本身的错误（我的猜测）还是在我的测试用例中？

提前非常感谢，这写起来真的很有趣，我迫不及待地想从事其他工作，但只有在我完成这项工作之后。