数学算法
*最大公约数算法(GCD)－特殊福利：最小公倍数算法。
*排列组合算法－还记得高中学过排列组合数学吗？
*调度场算法－用于将中缀表达式转换为后缀表达式的经典算法。
最大公约数算法（Greatest Common Divisor）
两个数字a和b的 最大公约数（或最大公因数）是将a和b整除都没有余数的最大正整数。
例如，gcd(39, 52) = 13，因为13除以39(39/13 = 3)以及52(52/13 = 4)，而且没有比13更大的数字。
在某些时候你可能不得不在学校里了解这一点。:-)
找到两个数字的GCD的费力方法是先找出两个数字的因子，然后取其共同的最大数。 问题在于分解数字是非常困难的，特别是当它们变大时。 （从好的方面来说，这种困难也是保证您的在线支付安全的原因。）
有一种更聪明的方法来计算GCD：欧几里德的算法。 这个算法主要观点是，
gcd(a, b) = gcd(b, a % b)其中a％b是a除以b的余数。
以下是Swift中这个想法的实现：
func gcd(_ a: Int, _ b: Int) -> Int {
let r = a % b
if r != 0 {
return gcd(b, r)
} else {
return b
}
}在 playground 上，试试一些例子：
gcd(52, 39) // 13
gcd(228, 36) // 12
gcd(51357, 3819) // 57让我们分步完成第三个例子：
gcd(51357, 3819)根据欧几里德的规则，这相当于，
gcd(3819, 51357 % 3819) = gcd(3819, 1710)因为51357 ％ 3819的余数是1710。 详细计算为51357 = (13 * 3819) + 1710，但我们只关心余数部分。
所以gcd(51357, 3819)与gcd(3819, 1710)相同。 这很有用，因为我们可以继续简化：
gcd(3819, 1710) = gcd(1710, 3819 % 1710) =
gcd(1710, 399) = gcd(399, 1710 % 399) =
gcd(399, 114) = gcd(114, 399 % 114) =
gcd(114, 57) = gcd(57, 114 % 57) =
gcd(57, 0)现在不能再进一步划分了。 114 / 57的余数为零，因为114 = 57 * 2。 这意味着我们找到了答案：
gcd(3819, 51357) = gcd(57, 0) = 57因此，在欧几里德算法的每个步骤中，数字变得更小，并且在某个点上，当它们中的一个变为零时它结束。
顺便说一下，两个数字的GCD也可能为1.它们被认为是 互素（译注：也叫互质）。 当没有数字将它们整除时会发生这种情况，例如：
gcd(841, 299) // 1下面是欧几里德算法略微不同的一种实现。 与第一个版本不同，它不使用递归，而只使用基本的while循环。
func gcd(_ m: Int, _ n: Int) -> Int {
var a = 0
var b = max(m, n)
var r = min(m, n)
while r != 0 {
a = b
b = r
r = a % b
}
return b
}函数顶部的 max() 和 min() 确保我们总是用较大的数字除以较小的数字。
最小公倍数
与GCD相关的想法是 最小公倍数 或叫做LCM。
两个数字a和b的最小公倍数是两者的倍数中最小的正整数。 换句话说，LCM可以被a和b整除。
例如：lcm(2, 3) = 6，因为6可以被2整除，也可以被3整除。
我们也可以使用欧几里德算法计算LCM：
a * b
lcm(a, b) = ---------
gcd(a, b)代码：
func lcm(_ m: Int, _ n: Int) -> Int {
return m / gcd(m, n) * n
}在playground中测试：
lcm(10, 8) // 40您可能不需要在任何实际问题中使用GCD或LCM，但是使用这种古老的算法很酷。 它首先由欧几里德在公元前300年左右他的书籍元素中描述。 有传言说他在攻击他的Commodore 64时，发现了这个算法。
Permutations
排列组合算法
A permutation is a certain arrangement of the objects from a collection. For example, if we have the first five letters from the alphabet, then this is a permutation:
排列是来自集合的对象的特定排列。 例如，如果我们有字母表中的前五个字母，那么这是一个排列：
a, b, c, d, eThis is another permutation:
这是另一个排列：
b, e, d, a, cFor a collection of n objects, there are n! possible permutations, where ! is the "factorial" function. So for our collection of five letters, the total number of permutations you can make is:
对于n对象的集合，有n!可能的排列，其中!是“阶乘”函数。 因此，对于我们五个字母的集合，您可以进行的排列总数为：
5! = 5 * 4 * 3 * 2 * 1 = 120A collection of six items has 6! = 720 permutations. For ten items, it is 10! = 3,628,800. That adds up quick!
六项的集合有6! = 720排列。 对于十项，有10! = 3,628,800。 这变化非常快！
Where does this n! come from? The logic is as follows: we have a collection of five letters that we want to put in some order. To do this, you need to pick up these letters one-by-one. Initially, you have the choice of five letters: a, b, c, d, e. That gives 5 possibilities.
这个n!来自哪里？ 逻辑如下：我们有一个五个字母的集合，我们想按顺序放置。 要做到这一点，你需要逐个拿起这些字母。 最初，您可以选择五个字母：a, b, c, d, e。 这提供了5种可能性。
After picking the first letter, you only have four letters left to choose from. That gives 5 * 4 = 20 possibilities:
选择第一个字母后，您只剩下四个字母可供选择。 这给了5 * 4 = 20的可能性：
a+b b+a c+a d+a e+a
a+c b+c c+b d+b e+b
a+d b+d c+d d+c e+c
a+e b+e c+e d+e e+dAfter picking the second letter, there are only three letters left to choose from. And so on... When you get to the last letter, you don't have any choice because there is only one letter left. That's why the total number of possibilities is 5 * 4 * 3 * 2 * 1.
选择第二个字母后，只剩下三个字母可供选择。 等等......当你到达最后一字母时，你没有任何选择，因为只留下一字母。 这就是为什么总的可能性是5 * 4 * 3 * 2 * 1。
To calculate the factorial in Swift:
在Swift中计算阶乘：
func factorial(_ n: Int) -> Int {
var n = n
var result = 1
while n > 1 {
result *= n
n -= 1
}
return result
}Try it out in a playground:
factorial(5) // returns 120Note that factorial(20) is the largest number you can calculate with this function, or you'll get integer overflow.
请注意，factorial(20)是您可以使用此函数计算的最大数字，否则您将获得整数溢出。
Let's say that from that collection of five letters you want to choose only 3 elements. How many possible ways can you do this? Well, that works the same way as before, except that you stop after the third letter. So now the number of possibilities is 5 * 4 * 3 = 60.
让我们说从五个字母的集合中你只想选择3个元素。 你可以用多少种方法做到这一点？ 好吧，除了你在第三个字母之后停止之外，它的工作方式和以前一样。 所以现在可能的数量是5 * 4 * 3 = 60。
The formula for this is:
这个公式是：
n!
P(n, k) = --------
(n - k)!where n is the size of your collection and k is the size of the group that you're selecting. In our example, P(5, 3) = 5! / (5 - 3)! = 120 / 2 = 60.
其中n是你的集合的大小，k是你选择的组的大小。 在我们的例子中，P(5, 3) = 5! / (5 - 3)! = 120 / 2 = 60。
You could implement this in terms of the factorial() function from earlier, but there's a problem. Remember that factorial(20) is the largest possible number it can handle, so you could never calculate P(21, 3), for example.
您可以根据之前的factorial()函数实现这一点，但是存在问题。 请记住，factorial(20)是它可以处理的最大可能数，所以你永远不能计算P(21, 3)。
Here is an algorithm that can deal with larger numbers:
这是一个可以处理更大数字的算法：
func permutations(_ n: Int, _ k: Int) -> Int {
var n = n
var answer = n
for _ in 1..<k {
n -= 1
answer *= n
}
return answer
}Try it out:
permutations(5, 3) // returns 60
permutations(50, 6) // returns 11441304000
permutations(9, 4) // returns 3024This function takes advantage of the following algebra fact:
此函数利用以下代数事实：
9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
P(9, 4) = --------------------------------- = 9 * 8 * 7 * 6 = 3024
5 * 4 * 3 * 2 * 1The denominator cancels out part of the numerator, so there's no need to perform a division and you're not dealing with intermediate results that are potentially too large.
分母取消了分子的一部分，因此不需要执行除法，也不需要处理可能太大的中间结果。
However, there are still limits to what you can calculate; for example the number of groups of size 15 that you can make from a collection of 30 objects -- i.e. P(30, 15) -- is ginormous and breaks Swift. Huh, you wouldn't think it would be so large but combinatorics is funny that way.
但是，您可以计算的内容仍有限制; 例如，你可以从30个对象的集合中获得的大小为15的组的数量 - 即P（30, 15） - 是巨大的并且打破了Swift。 嗯，你不会认为它会如此之大，但组合学很有趣。
Generating the permutations
生成排列
So far we've counted how many permutations exist for a given collection, but how can we actually create a list of all these permutations?
到目前为止，我们已经计算了给定集合存在多少排列，但我们如何才能真正创建所有这些排列的列表？
Here's a recursive algorithm by Niklaus Wirth:
这是Niklaus Wirth的递归算法：
func permuteWirth<T>(_ a: [T], _ n: Int) {
if n == 0 {
print(a) // display the current permutation
} else {
var a = a
permuteWirth(a, n - 1)
for i in 0..<n {
a.swapAt(i, n)
permuteWirth(a, n - 1)
a.swapAt(i, n)
}
}
}Use it as follows:
let letters = ["a", "b", "c", "d", "e"]
permuteWirth(letters, letters.count - 1)This prints all the permutations of the input array to the debug output:
这会将输入数组的所有排列打印到调试输出：
["a", "b", "c", "d", "e"]
["b", "a", "c", "d", "e"]
["c", "b", "a", "d", "e"]
["b", "c", "a", "d", "e"]
["a", "c", "b", "d", "e"]
...As we've seen before, there will be 120 of them.
正如我们之前看到的，将会有120个。
How does the algorithm work? Good question! Let's step through a simple example with just three elements. The input array is:
算法如何工作？ 好问题！ 让我们通过一个只有三个元素的简单示例。 输入数组是：
[ "x", "y", "z" ]We're calling it like so:
我们这样称呼它：
permuteWirth([ "x", "y", "z" ], 2)Note that the n parameter is one less than the number of elements in the array!
请注意，n参数比数组中的元素数少一个！
After calling permuteWirth() it immediately calls itself recursively with n = 1. And that immediately calls itself recursively again with n = 0. The call tree looks like this:
在调用permuteWirth()之后，它立即用n = 1递归调用自身。 然后用n = 0再次递归地调用自身。 调用树看起来像这样：
permuteWirth([ "x", "y", "z" ], 2)
permuteWirth([ "x", "y", "z" ], 1)
permuteWirth([ "x", "y", "z" ], 0) // prints ["x", "y", "z"]When n is equal to 0, we print out the current array, which is still unchanged at this point. The recursion has reached the base case, so now we go back up one level and enter the for loop.
当n等于0时，我们打印出当前数组，此时该数组仍未改变。 递归已达到基本情况，所以现在我们回到一个级别并进入for循环。
permuteWirth([ "x", "y", "z" ], 2)
permuteWirth([ "x", "y", "z" ], 1) <--- back to this level
swap a[0] with a[1]
permuteWirth([ "y", "x", "z" ], 0) // prints ["y", "x", "z"]
swap a[0] and a[1] backThis swapped "y" and "x" and printed the result. We're done at this level of the recursion and go back to the top. This time we do two iterations of the for loop because n = 2 here. The first iteration looks like this:
这交换了"y"和"x"并打印结果。 我们在递归的这个级别完成并返回顶部。 这次我们对for循环进行两次迭代，因为这里的n = 2。 第一次迭代看起来像这样：
permuteWirth([ "x", "y", "z" ], 2) <--- back to this level
swap a[0] with a[2]
permuteWirth([ "z", "y", "x" ], 1)
permuteWirth([ "z", "y", "x" ], 0) // prints ["z", "y", "x"]
swap a[0] with a[1]
permuteWirth([ "y", "z", "x" ], 0) // prints ["y", "z", "x"]
swap a[0] and a[1] back
swap a[0] and a[2] backAnd the second iteration:
第二次迭代：
permuteWirth([ "x", "y", "z" ], 2)
swap a[1] with a[2] <--- second iteration of the loop
permuteWirth([ "x", "z", "y" ], 1)
permuteWirth([ "x", "z", "y" ], 0) // prints ["x", "z", "y"]
swap a[0] with a[1]
permuteWirth([ "z", "x", "y" ], 0) // prints ["z", "x", "y"]
swap a[0] and a[1] back
swap a[1] and a[2] backTo summarize, first it swaps these items:
总而言之，首先它交换这些项目：
[ 2, 1, - ]Then it swaps these:
然后它交换这些：
[ 3, -, 1 ]Recursively, it swaps the first two again:
递归地，它再次交换前两个：
[ 2, 3, - ]Then it goes back up one step and swaps these:
然后它回到一步并交换这些：
[ -, 3, 2 ]And finally the first two again:
最后是前两个：
[ 3, 1, - ]Of course, the larger your array is, the more swaps it performs and the deeper the recursion gets.
当然，您的数组越大，它执行的交换越多，递归越深。
If the above is still not entirely clear, then I suggest you give it a go in the playground. That's what playgrounds are great for. :-)
如果以上仍然不完全清楚，那么我建议你在操场上试一试。 这就是 playgrounds 的特色。:-)
For fun, here is an alternative algorithm, by Robert Sedgewick:
为了好玩，这是Robert Sedgewick的另一种算法：
func permuteSedgewick(_ a: [Int], _ n: Int, _ pos: inout Int) {
var a = a
pos += 1
a[n] = pos
if pos == a.count - 1 {
print(a) // display the current permutation
} else {
for i in 0..<a.count {
if a[i] == 0 {
permuteSedgewick(a, i, &pos)
}
}
}
pos -= 1
a[n] = 0
}You use it like this:
let numbers = [0, 0, 0, 0]
var pos = -1
permuteSedgewick(numbers, 0, &pos)The array must initially contain all zeros. 0 is used as a flag that indicates more work needs to be done on each level of the recursion.
该数组最初必须包含全零。 0用作标志，指示需要在递归的每个级别上完成更多工作。
The output of the Sedgewick algorithm is:
Sedgewick算法的输出是：
[1, 2, 3, 0]
[1, 2, 0, 3]
[1, 3, 2, 0]
[1, 0, 2, 3]
[1, 3, 0, 2]
...It can only deal with numbers, but these can serve as indices into the actual array you're trying to permute, so it's just as powerful as Wirth's algorithm.
它只能处理数字，但是它们可以作为你试图置换的实际数组的索引，所以它和Wirth的算法一样强大。
Try to figure out for yourself how this algorithm works!
试着弄清楚这个算法是如何工作的！
Combinations
组合
A combination is like a permutation where the order does not matter. The following are six different permutations of the letters k l m but they all count as the same combination:
组合就像排列无关紧要的排列。 以下是字母k l m的六种不同排列，但它们都算作相同的组合：
k, l, m k, m, l m, l, k
l, m, k l, k, m m, k, lSo there is only one combination of size 3. However, if we're looking for combinations of size 2, we can make three:
因此，只有一个大小为3的组合。但是，如果我们正在寻找大小为2的组合，我们可以制作三个：
k, l (is the same as l, k)
l, m (is the same as m, l)
k, m (is the same as m, k)The C(n, k) function counts the number of ways to choose k things out of n possibilities. That's why it's also called "n-choose-k". (A fancy mathematical term for this number is "binomial coefficient".)C(n, k)函数计算从n可能性中选择k事物的方式的数量。 这就是为什么它也被称为"n-choose-k"。 （这个数字的奇特数学术语是“二项式系数”。）
The formula for C(n, k) is:C(n, k)的公式：
n! P(n, k)
C(n, k) = ------------- = --------
(n - k)! * k! k!As you can see, you can derive it from the formula for P(n, k). There are always more permutations than combinations. You divide the number of permutations by k! because a total of k! of these permutations give the same combination.
如您所见，您可以从P(n, k)的公式推导出它。 总是有更多的排列而不是组合。 你将排列数除以k!，因为这些排列的总共k!给出了相同的组合。
Above I showed that the number of permutations of k l m is 6, but if you pick only two of those letters the number of combinations is 3. If we use the formula we should get the same answer. We want to calculate C(3, 2) because we choose 2 letters out of a collection of 3.
上面我展示了k l m的排列数是6，但是如果你只选择其中两个字母，那么组合的数量是3.如果我们使用公式，我们应该得到相同的答案。 我们想要计算C(3, 2)因为我们从3的集合中选择2个字母。
3 * 2 * 1 6
C(3, 2) = --------- = --- = 3
1! * 2! 2Here's a simple function to calculate C(n, k):
这是一个计算 C(n, k) 的简单函数：
func combinations(_ n: Int, choose k: Int) -> Int {
return permutations(n, k) / factorial(k)
}Use it like this:
combinations(28, choose: 5) // prints 98280Because this uses the permutations() and factorial() functions under the hood, you're still limited by how large these numbers can get. For example, combinations(30, 15) is "only" 155,117,520 but because the intermediate results don't fit into a 64-bit integer, you can't calculate it with the given function.
因为它在引擎盖下使用permutations()和factorial()函数，你仍然受限于这些数字可以得到多大。 例如，combinations(30, 15)是“仅” 155,117,520，但由于中间结果不适合64位整数，因此无法使用给定函数计算它。
There's a faster approach to calculate C(n, k) in O(k) time and O(1) extra space. The idea behind it is that the formula for C(n, k) is:
有一种更快的方法来计算O(k)时间和O(1)额外空间中的C(n, k)。 其背后的想法是C(n, k)的公式是：
n! n * (n - 1) * ... * 1
C(n, k) = ------------- = ------------------------------------------
(n - k)! * k! (n - k) * (n - k - 1) * ... * 1 * k!After the reduction of fractions, we get the following formula:
减少部分后，我们得到以下公式：
n * (n - 1) * ... * (n - k + 1) (n - 0) * (n - 1) * ... * (n - k + 1)
C(n, k) = --------------------------------------- = -----------------------------------------
k! (0 + 1) * (1 + 1) * ... * (k - 1 + 1)We can implement this formula as follows:
我们可以按如下方式实现这个公式：
func quickBinomialCoefficient(_ n: Int, choose k: Int) -> Int {
var result = 1
for i in 0..<k {
result *= (n - i)
result /= (i + 1)
}
return result
}This algorithm can create larger numbers than the previous method. Instead of calculating the entire numerator (a potentially huge number) and then dividing it by the factorial (also a very large number), here we already divide in each step. That causes the temporary results to grow much less quickly.
该算法可以创建比先前方法更大的数字。 而不是计算整个分子（一个潜在的巨大数字），然后将它除以阶乘（也是一个非常大的数字），这里我们已经分为每一步。 这导致临时结果增长得更快。
Here's how you can use this improved algorithm:
以下是使用此改进算法的方法：
quickBinomialCoefficient(8, choose: 2) // prints 28
quickBinomialCoefficient(30, choose: 15) // prints 155117520This new method is quite fast but you're still limited in how large the numbers can get. You can calculate C(30, 15) without any problems, but something like C(66, 33) will still cause integer overflow in the numerator.
这种新方法速度非常快，但您仍然可以限制数量的大小。 你可以毫无问题地计算C(30, 15)，但像C(66, 33)这样的东西仍然会导致分子中的整数溢出。
Here is an algorithm that uses dynamic programming to overcome the need for calculating factorials and doing divisions. It is based on Pascal's triangle:
这是一种算法，它使用动态编程来克服计算阶乘和分割的需要。 它基于Pascal的三角形：
0: 1
1: 1 1
2: 1 2 1
3: 1 3 3 1
4: 1 4 6 4 1
5: 1 5 10 10 5 1
6: 1 6 15 20 15 6 1Each number in the next row is made up by adding two numbers from the previous row. For example in row 6, the number 15 is made by adding the 5 and 10 from row 5. These numbers are called the binomial coefficients and as it happens they are the same as C(n, k).
下一行中的每个数字都是通过添加前一行中的两个数字来组成的。例如，在第6行中，数字15是通过从第5行添加5和10来产生的。这些数字称为二项式系数，并且它们与C(n, k)相同。
For example, for row 6:
C(6, 0) = 1
C(6, 1) = 6
C(6, 2) = 15
C(6, 3) = 20
C(6, 4) = 15
C(6, 5) = 6
C(6, 6) = 1The following code calculates Pascal's triangle in order to find the C(n, k) you're looking for:
下面的代码计算Pascal的三角形，以便找到你正在寻找的 C(n, k)：
func binomialCoefficient(_ n: Int, choose k: Int) -> Int {
var bc = Array(repeating: Array(repeating: 0, count: n + 1), count: n + 1)
for i in 0...n {
bc[i][0] = 1
bc[i][i] = 1
}
if n > 0 {
for i in 1...n {
for j in 1..<i {
bc[i][j] = bc[i - 1][j - 1] + bc[i - 1][j]
}
}
}
return bc[n][k]
}The algorithm itself is quite simple: the first loop fills in the 1s at the outer edges of the triangle. The other loops calculate each number in the triangle by adding up the two numbers from the previous row.
算法本身非常简单：第一个循环填充三角形外边缘的1s。 其他循环通过将前一行中的两个数字相加来计算三角形中的每个数字。
Now you can calculate C(66, 33) without any problems:
现在你可以毫无问题地计算 C(66, 33)：
binomialCoefficient(66, choose: 33) // prints a very large numberYou may wonder what the point is in calculating these permutations and combinations, but many algorithm problems are really combinatorics problems in disguise. Often you may need to look at all possible combinations of your data to see which one gives the right solution. If that means you need to search through n! potential solutions, you may want to consider a different approach -- as you've seen, these numbers become huge very quickly!
您可能想知道计算这些排列和组合的重点是什么，但许多算法问题实际上是伪装的组合问题。通常，您可能需要查看数据的所有可能组合，以查看哪个组合能够提供正确的解决方案。如果这意味着您需要搜索 n! 潜在的解决方案，您可能需要考虑一种不同的方法 - 正如您所见，这些数字变得非常快！
References
参考
Wirth's and Sedgewick's permutation algorithms and the code for counting permutations and combinations are based on the Algorithm Alley column from Dr.Dobb's Magazine, June 1993. The dynamic programming binomial coefficient algorithm is from The Algorithm Design Manual by Skiena.
Wirth和Sedgewick的排列算法以及计数排列和组合的代码基于Dr.Dobb杂志1993年6月的算法Alley专栏。动态编程二项系数算法来自Skiena的算法设计手册。
Written for Swift Algorithm Club by Matthijs Hollemans and Kanstantsin Linou
Shunting Yard Algorithm
调度场算法
Any mathematics we write is expressed in a notation known as infix notation. For example:
我们编写的任何数学都用一种称为中缀符号的符号表示。 例如：
A + B * C
The operator is placed in between the operands, hence the expression is said to be in infix form. If you think about it, any expression that you write on a piece of paper will always be in infix form. This is what we humans understand.
操作符位于操作数之间，因此表达式被称为infix形式。 如果你考虑一下，你在一张纸上写的任何表达都将是中缀形式。 这是我们人类所理解的。
Multiplication has higher precedence than addition, so when the above expression is evaluated you would first multiply B and C, and then add the result to A. We humans can easily understand the precedence of operators, but a machine needs to be given instructions about each operator.
乘法具有比加法更高的优先级，因此当评估上述表达式时，首先将B和C相乘，然后将结果添加到A。我们人类可以很容易地理解运算符的优先级，但是需要为机器提供有关每个运算符的指令。
To change the order of evaluation, we can use parentheses:
要更改计算顺序，我们可以使用括号：
(A + B) * C
Now A is first added to B and then the sum is multiplied by C.
现在A首先加到B然后总和乘以C。
If you were to write an algorithm that parsed and evaluated expressions in infix notation you will realize that it's a tedious process. You'd have to parse the expression multiple times to know what operation to perform first. As the number of operators increase so does the complexity.
如果您要编写一个以中缀表示法解析和计算表达式的算法，您将意识到这是一个繁琐的过程。 您必须多次解析表达式才能知道首先要执行的操作。 随着运营商数量的增加，复杂性也随之增加。
Postfix notation
Postfix表示法
In postfix notation, also known as Reverse Polish Notation or RPN, the operators come after the corresponding operands. Here is the postfix representation of the example from the previous section:
在后缀表示法（也称为反向波兰表示法或RPN）中，运算符位于相应的操作数之后。 以下是上一节中示例的后缀表示：
A B C * +
An expression in postfix form will not have any parentheses and neither will you have to worry about scanning for operator precedence. This makes it easy for the computer to evaluate expressions, since the order in which the operators need to be applied is fixed.
后缀形式的表达式不会有任何括号，您也不必担心扫描运算符优先级。 这使得计算机可以很容易地计算表达式，因为需要应用运算符的顺序是固定的。
Evaluating a postfix expression is easily done using a stack. Here is the pseudocode:
Read the postfix expression token by token
If the token is an operand, push it onto the stack
If the token is a binary operator,
Pop the two topmost operands from the stack
Apply the binary operator to the two operands
Push the result back onto the stack
Finally, the value of the whole postfix expression remains in the stack
使用堆栈可以轻松地评估后缀表达式。 这是伪代码：
通过令牌读取后缀表达式标记
如果令牌是操作数，则将其推入堆栈
如果令牌是二元运算符，
1. 从堆栈中弹出两个最顶层的操作数
2. 将二元运算符应用于两个操作数
3. 将结果推回堆栈最后，整个后缀表达式的值保留在堆栈中
Using the above pseudocode, the evaluation of A B C * + would be as follows:
使用上述伪代码，A B C * +的评估如下：
| Expression | Stack |
|---|---|
| A B C * + | |
| B C * + | A |
| C * + | A, B |
| * + | A, B, C |
| + | A, D |
| E |
Where D = B * C and E = A + D.
As seen above, a postfix operation is relatively easy to evaluate as the order in which the operators need to be applied is pre-decided.
如上所述，后缀操作相对容易评估，因为预先决定了运算符需要应用的顺序。
Converting infix to postfix
将中缀转换为后缀
The shunting yard algorithm was invented by Edsger Dijkstra to convert an infix expression to postfix. Many calculators use this algorithm to convert the expression being entered to postfix form.
分流码算法是由Edsger Dijkstra发明的，用于将中缀表达式转换为后缀。 许多计算器使用此算法将输入的表达式转换为后缀形式。
Here is the psedocode of the algorithm:
For all the input tokens:
Read the next token
If token is an operator (x)
While there is an operator (y) at the top of the operators stack and either (x) is left-associative and its precedence is less or equal to that of (y), or (x) is right-associative and its precedence is less than (y)
Pop (y) from the stack
Add (y) output buffer
Push (x) on the stack
Else if token is left parenthesis, then push it on the stack
Else if token is a right parenthesis
Until the top token (from the stack) is left parenthesis, pop from the stack to the output buffer
Also pop the left parenthesis but don’t include it in the output buffer
Else add token to output buffer
Pop any remaining operator tokens from the stack to the output
这是算法的psedocode：
对于所有输入令牌：
1. 阅读下一个标记
2. 如果令牌是运营商（x）
1. 虽然在运算符堆栈的顶部有一个运算符（y），并且（x）是左关联的，其优先级小于或等于（y）的优先级，或者（x）是右关联的，并且 优先级小于（y）
1. 从堆栈中弹出（y）
2. 添加（y）输出缓冲区
2. 按（x）在堆栈上
3. 否则，如果令牌是左括号，则将其推入堆栈
4. 否则，如果令牌是右括号
1. 在顶部令牌（来自堆栈）左括号之前，从堆栈弹出到输出缓冲区
2. 同时弹出左括号，但不要将其包含在输出缓冲区中
7. 否则将令牌添加到输出缓冲区将任何剩余的操作符标记从堆栈弹出到输出
Let's take a small example and see how the pseudocode works. Here is the infix expression to convert:
让我们举一个小例子，看看伪代码是如何工作的。 这是要转换的中缀表达式：
4 + 4 * 2 / ( 1 - 5 )
The following table describes the precedence and the associativity for each operator. The same values are used in the algorithm.
下表描述了每个运算符的优先级和关联性。 算法中使用相同的值。
| Operator | Precedence | Associativity |
|---|---|---|
| ^ | 10 | Right |
| * | 5 | Left |
| / | 5 | Left |
| + | 0 | Left |
| - | 0 | Left |
Here we go:
| Token | Action | Output | Operator stack |
|---|---|---|---|
| 4 | Add token to output | 4 | |
| + | Push token to stack | 4 | + |
| 4 | Add token to output | 4 4 | + |
| * | Push token to stack | 4 4 | * + |
| 2 | Add token to output | 4 4 2 | * + |
| / | Pop stack to output, Push token to stack | 4 4 2 * | / + |
| ( | Push token to stack | 4 4 2 * | ( / + |
| 1 | Add token to output | 4 4 2 * 1 | ( / + |
| - | Push token to stack | 4 4 2 * 1 | - ( / + |
| 5 | Add token to output | 4 4 2 * 1 5 | - ( / + |
| ) | Pop stack to output, Pop stack | 4 4 2 * 1 5 - | / + |
| end | Pop entire stack to output | 4 4 2 * 1 5 - / + |
We end up with the postfix expression:
我们最终得到了后缀表达式：
4 4 2 * 1 5 - / +
See also
扩展阅读
Shunting yard algorithm on Wikipedia
调度场算法的维基百科
Written for the Swift Algorithm Club by Ali Hafizji
Migrated to Swift 3 by Jaap Wijnen