问题标签 [shunting-yard]

我正在构建一个高级数学解析器，并且想知道 Shunting-Yard 和其他可用解析器算法（如“Descent Parser”）之间的区别，因为我更喜欢将公式存储在 RPN 表示法中。

提前致谢，

我稍微修改了这个算法来处理大括号和方括号

出于某种原因，当我输入以下内容时： 10 - [ ( 3 - 2 ) * 10 ] / 5
输出为： 10 3 2 - 10 * - 5 /

当输出应该是：10 3 2 - 10 * 5 / -

关于如何正确修改它以处理大括号{}和括号[]的任何想法？

如何扩展调车场算法，这原本是为了让二元运算符支持条件三元运算符（“a？b：c”）？我还没有在这里看到这个问题的答案，我有一个，所以我发布它。

有关上下文，请先阅读有关三元运算符的这个问题。

我正在构建自己的编程语言，允许您定义自定义运算符。因为我希望它有尽可能少的编译器内置，它应该允许自定义三元运算符的定义，最好是在形式

我的（手写的）表达式解析器会将嵌套的三元运算符转换为由运算符分隔的操作数列表。

这OperatorChain现在从范围内的运算符定义中查找运算符，并使用修改后的调车场算法将列表转换为二进制 AST 节点，如下所示：

我需要如何修改此算法以使用三元运算符，包括自定义运算符？

根据维基百科，调车码算法用于解析数学表达式。但是有什么理由不能将它与逻辑和算术表达式以及比较一起使用吗？

例如，可以用它来解析这个：

据我所知，您可以将逻辑运算符定义为具有最低优先级，然后是比较运算符，然后将通常的算术运算符定义为优先级增加。还是我错过了什么？

我有一个命题逻辑公式

((a or b) and !d) or e -> c

怎么可能解析这个字符串，所以我可以制作一个真值树？

我想我应该用->,and和分割我的字符串or，但它会弄乱括号。在拆分字符串之前如何保护每个括号？在做任何其他事情之前，我是否应该使用正则表达式拆分括号中的表达式？

对于我示例中的字符串，我想它应该创建一个嵌套数组，其中['or', a, b]'deepest' 级别存储在 'next most deep level'['and', ['or', a, b]]中。所以我的猜测是这个字符串应该被转换为一个数组

其中每个数组由 3 个元素组成，其中第一个元素告诉操作员，接下来的两个元素告诉操作员应该处理哪些“命题”。

我不确定这是否是一个聪明的结构，但我想这可能是解析字符串的一种方法。

我研究了将中缀转换为后缀表示法或抽象语法树 (AST) 的调车场算法。我应该使用类似的东西来正确地做到这一点吗？

你能告诉我是我理解错了还是例子错了？

我将在运算符之后立即编写关联性。'r' 代表右，'l' 代表左。表达式不会有括号。

-r *r 8 5 +r /r 20 4 /l *r 5 8 10

给出的结果是这样的：

8 5 *r 20 4 /r 5 8 *r 10 /l +r -r

我不明白的是，当我5 8 10此时到达我的堆栈时会是*r /l +r -r。我读了5，它不是运算符，所以我打印它。我读的是 8，而不是运算符-> 打印。然后我读了 10，而不是运算符 -> 打印。为什么 *r 在读取 10 之前会从堆栈中弹出？

我试图弄清楚在实现关闭码算法时不同运营商的优先级是什么。

我的抽象语法树在中缀中，我正在使用关闭码算法进行评估。这适用于算术运算符。我面临的问题是我不知道所有其他运算符的优先级。

从https://en.wikipedia.org/wiki/Shunting-yard_algorithm我可以看到以下操作适用于这些运算符。数字是优先级。

但是我似乎找不到任何描述关系运算符和逻辑运算符的先例的东西？我已经搜索了很多答案。

有人可以给我所有这些运算符的先例的完整图片：

提前致谢。

/布莱恩

除了 Dijkstra 调车场算法之外，还有什么方法可以将中缀转换为 RPN 吗？我试图通过将其与另一种转换方法进行比较来研究调车场算法的弱点和优势。非常感谢任何与调车场算法期刊的链接。谢谢

如何修改标准的调车场算法以包含一个“墙”符号 |，表示函数参数的结束？也就是说，支持修改后缀表示法（反向波兰表示法），它允许函数具有任意数量的参数。

修改后缀表示法的几个示例：

f (1,2)+9 ⟶ | 1 2 f 9 +
f (1,2,3)+9 ⟶ | 1 2 3 9 +

拜托，我正在寻找实际的修改，而不仅仅是关于如何做的想法。

调车场算法

1. 虽然有要读取的令牌：
2. 读取令牌。
3. 如果令牌是数字，则将其推送到输出队列。
4. 如果令牌是函数令牌，则将其压入堆栈。
5. 如果标记是函数参数分隔符（例如，逗号）：
   • 直到堆栈顶部的标记是左括号，将操作符从堆栈中弹出到输出队列中。如果没有遇到左括号，则分隔符放错位置或括号不匹配。

6. 如果令牌是运算符 o1，则：

   • 虽然有一个操作员令牌 o2，但在操作员堆栈的顶部，或者

     • o1 是左结合的，它的优先级小于或等于 o2 的优先级，或者

     • o1 是右结合的，并且优先级低于 o2，

       -pop o2 从算子栈中弹出到输出队列中；

     • 在迭代结束时，将 o1 推入运算符堆栈。
7. 如果令牌是左括号（即“（”），则将其压入堆栈。
8. 如果标记是右括号（即“）”）：
   • 直到堆栈顶部的标记是左括号，将操作符从堆栈中弹出到输出队列中。
   • 从堆栈中弹出左括号，但不在输出队列中。
   • 如果堆栈顶部的令牌是函数令牌，则将其弹出到输出队列中。
   • 如果堆栈用完而没有找到左括号，则存在不匹配的括号。
9. 当没有更多要读取的令牌时：
   • 虽然堆栈中仍有操作符标记：
     • 如果栈顶的操作符记号是括号，则括号不匹配。
     • 将操作员弹出到输出队列中。
10. 出口。