调车场算法

数学表达式的写法是中缀表示法。运算符具有优先级，括号覆盖该优先级。许多程序需要动态地进行解析计算。一个很好的方法是将中缀表示法转换为某种中间格式。在本例中，我们将使用一种非常常见和简单的格式，称为逆波兰表示法．

的调车场算法是解析包含不同优先级的二元运算符的中缀表达式的一种简单技术。通常，算法给每个操作符分配正确的操作数，考虑到优先级的顺序。因此，可以用它立即对表达式求值，将其转换为后缀，或构造相应的语法树。

Shunting Yard算法不是Mergeort，String搜索等的基本算法。它是堆栈，队列和阵列的完全高级，所有算法都包含在相同的算法中。虽然算法本身非常简单，但是一个坚实的灵活实现可能是数千行代码。

在我们有程序计算表达式之前，我们需要将它们转换为中间表示法，其中运算符按照它们的顺序执行。与看他们头部中的infix表达的人类不同，必须明确讲述计算机的顺序应该是什么。最常见的中间格式是反向抛光。

使用的程序如下:

• 表达式从左到右解析。
• 每次读取数字或操作数时，都将其压入堆栈。
• 每次出现一个操作符时，我们从堆栈中弹出所需的操作数，执行操作，并将结果推回堆栈。
• 当没有符号(数字、运算符或任何其他数学符号)可读时，我们就完成了。堆栈上的最后一个数字就是结果。

考虑以下中缀符号:

$4 + 18 /(9 - 3)。$

现在我们知道，根据运算规则或顺序，答案是 $7$．

我们还没有看到，给定上面的中缀符号，分流码算法将输出反向波兰符号为

$4、18、9、3、-、/、+$

注意，逗号不是反向优化的一部分，而是用于分隔每个标记。

使用反向抛光的程序，

在步骤 $一个$来 $d$，我们将反向优化表达式中的数字压入堆栈。在步骤 $e$，我们已经到达了操作员标志 $（-）$，我们取出涉及的两个数字，执行操作 $9 - 3 = 6$，并将其推回堆栈。接下来是运算符 $（/）$在那里我们弹出 $6$和 $18$然后执行操作 $18/6 = 3$然后把它压入堆栈。我们继续这个过程，直到我们只剩下一个数字 $7$．

为了构建算法，我们需要

• 操作栈
• 1个输出队列
• 一个令牌数组(或其他列表)。

算法的伪代码如下:

12 3 4 5 6 7 8 9 10 11 12 13

1.当有令牌可读时:2。读一个token 3。如果它是一个数字，将它添加到队列4。如果它是一个算子。而栈顶有一个优先级更高的操作符:6。从堆栈中弹出操作符到输出队列7。将当前操作符压入堆栈8。如果它是一个左括号，将它推到堆栈9。如果是右括号10。 While there's not a left bracket at the top of the stack: 11. Pop operators from the stack onto the output queue. 12. Pop the left bracket from the stack and discard it 13. While there are operators on the stack, pop them to the queue

算法相当简单。再次考虑中缀表示法。为了解决这个问题，让我们建立一个由列表、堆栈和队列组成的数组。

左边的标记列表是从下到上填充的，与前面声明的中缀表达式相同。我们现在要根据分流码算法，从下往上填充堆栈和队列。

我们从下往上读代币，所以数字 $4$转到输出队列。下一个元素是一个运算符 $（+）$，按算法排列 $4、5$和 $6，$将被推入堆栈，因为空堆栈没有任何优先级元素。

由于加法运算符的优先级低于除法运算符，因此忽略行 $5$和 $6$．当我们得到一个左括号时，我们将它压入堆栈，当我们得到一个右括号时，根据lines $10$和 $11，$我们将操作符从堆栈中弹出到输出队列中，直到到达左括号。然后我们抛弃左括号。

最后，当堆栈中剩下操作符时，我们将它们取出到队列中。

就是这样:输出队列包含反向波兰表示法，正如我们已经看到的，可以通过计算得出最终答案。