介绍 (Introduction)

As a coder, you’re probably used to telling computers what to do. Type up some code, run it, and the computer gets to work executing whatever command you gave it.

作为编码员，您可能习惯于告诉计算机该怎么做。 输入一些代码，运行它，然后计算机就会开始执行您所给定的任何命令。

Even though we have this powerful reign over computers, there’s still a lot of magic constantly occurring in our code that we tend to overlook. This is especially true if you’re working with high-level languages with pre-built functions, as most of us are. And of course while there’s no real reason to reinvent the wheel or try to implement these helpful functions on your own, it’s still fun to take a peek under the hood and see what’s going on!

即使我们拥有对计算机的强大控制能力，但是在我们的代码中仍然经常发生很多不可忽视的魔术。 如果您像我们大多数人一样使用具有预构建功能的高级语言，则尤其如此。 当然，虽然没有真正的理由重新发明轮子或尝试自己实现这些有用的功能，但是偷偷摸摸地看看发生了什么仍然很有趣！

Today we’re going to take a closer look at one of these seemingly obvious concepts that we’ve probably all used at one point or another: the order of operations.

今天，我们将仔细研究一下我们可能曾经在某一点或另一点全部使用过的这些看似显而易见的概念之一：操作顺序。

Say you want to evaluate this expression: 5 + 10 * 3. According to the mathematical order of operations, you should multiply 10 by 3 first and then add 5 to the product of that, but how exactly would you tell a computer to do this?

假设您要评估此表达式： 5 + 10 * 3 。 根据数学运算的顺序，您应该先将10 by 3乘以10 by 3 ，然后再将5乘以10 by 3的乘积，但是您如何准确地告诉计算机这样做呢？

There are a few different ways we can parse this equation, but some require a little more background than others.

我们可以使用几种不同的方法来解析此方程式，但是有些方法比其他方法需要更多的背景知识。

In this tutorial, you’ll see how to go about solving this.

在本教程中，您将了解如何解决这个问题。

This method requires that we first convert our equation into the correct format. Once it’s in a more machine readable form, then we can go ahead and feed it through our parsing algorithm which will actually calculate it.

此方法要求我们首先将方程式转换为正确的格式。 一旦采用机器可读的形式，我们就可以继续通过解析算法(实际会对其进行计算)进行处理。

First I’ll show you how to get the correct format so we can see what the end result should look like, then I’ll walk you through the actual algorithm used to evaluate the expression. Just to keep things simple, we’ll only be dealing with four operators in this example: addition, subtraction, multiplication, and division.

首先，我将向您展示如何获取正确的格式，以便我们可以看到最终结果应该是什么样子，然后再向您介绍用于评估表达式的实际算法。 为了简单起见，在此示例中，我们仅处理四个运算符：加，减，乘和除。

后缀中缀 (Infix to Postfix)

Even though you may not realize it yet, most of you are probably already familiar with infix notation. The above expression, 5 + 10 * 3, is written in infix notation. It just means the operators fall in between the operands that they’re acting upon.

即使您可能尚未意识到这一点，但大多数人可能已经熟悉infix表示法 。 上面的表达式5 + 10 * 3用中缀符号表示。 这仅表示运算符落在他们要操作的操作数之间 。

什么是后缀表示法？ (What is Postfix Notation?)

As mentioned earlier, we need to convert our equation into a format that the computer can easily understand. This format is called postfix notation.

如前所述，我们需要将方程式转换为计算机易于理解的格式。 此格式称为后缀表示法 。

Expressions written in postfix notation will have all operators following their operands.

用后缀表示法编写的表达式将使所有运算符跟随其操作数。

This is important because when the machine is reading expressions in this format, it will never encounter an operator before the operands it’s acting on, which means it won’t have to go back and forth.

这很重要，因为当机器读取这种格式的表达式时，它将永远不会遇到运算符，然后再对它进行操作，这意味着它不必来回移动。

So in the previous example, 5 + 10 * 3 becomes 5 10 3 * +.

因此，在前面的示例中， 5 + 10 * 3变为5 10 3 * + 。

This may look unusual, but there’s a methodology to arrive at this.

这看起来可能很不寻常，但是有一种方法可以解决这个问题。

从Infix转换为Postfix的人性化方式 (Human-Friendly Way to Convert from Infix to Postfix)

1. Add in parentheses in order of precedence
   按优先顺序添加括号

(5 + (10 * 3))

1. Move every operator to the right, directly before its closing parenthesis
   将每个运算符右移，紧接在右括号之前

(5 ( 10 3 *)+)

1. Now just drop the parentheses altogether, which leaves us with our expression in postfix notation
   现在，完全删除括号，这使我们可以使用后缀表示法表示

5 10 3 * +

Another example, just to show that the operators won’t necessarily always be at the very end:

再举一个例子 ，只是为了表明运算符不一定总是在最后：

8 * 4 + 2
    ((8 * 4) + 2)
    ((8 4 *) 2 +)
    8 4 * 2 +

Again, this isn’t really ideal for the computer to do. It still wouldn’t know where to put the parentheses. Luckily for us, we have a an algorithm to produce the same results.

同样，对于计算机而言，这并不是很理想。 它仍然不知道将括号放在何处。 对我们来说幸运的是，我们有一个算法可以产生相同的结果。

调车场算法 (Shunting Yard Algorithm)

The Shunting Yard Algorithm was developed by Dijkstra as a means to convert infix notation to postfix notation.

Dijkstra开发了Shunting Yard算法，以将中缀符号转换为后缀符号。

Before we go any further, let’s just quickly review the two data structures we’re going to be using here: a stack and a queue. We can use an array to hold both of these sets of data. The main difference comes from the order we’re adding and removing the data.

在继续之前，让我们快速回顾一下我们将在此处使用的两个数据结构：堆栈和队列。 我们可以使用数组来保存这两组数据。 主要区别在于我们添加和删除数据的顺序 。

Queue — When we add data to a queue, we’re pushing it onto the back. Just imagine you’re getting in line for an event and every person in line is an element in the queue. When you walk up to the line, you’re automatically inserted into the back of the line. As the event starts letting people in (removing elements from the queue), they pull from the front of the line since those people have been there longer. You can remember this with the acronym FIFO: first in, first out.

队列 -当我们将数据添加到队列时，我们会将其推后。 试想一下，您正在排队参加一个活动，排队的每个人都是队列中的一个元素。 当您走到生产线时，您会自动插入生产线的背面。 事件开始让人们进来(从队列中删除元素)时，他们从队列的最前面拉起，因为这些人在那里待了更长的时间。 您可以使用首字母缩写FIFO记住这一点：先进先出。

Stack — Every time we add a new element to the stack, it will be put on top (or at the front) instead of in the back. When we want to remove an item from the stack, we’ll pop off the top item. Because new elements always go on top, those new ones will always be popped off first when we need to remove something. This can be remembered with the acronym LIFO: last in, first out.

堆栈 -每次将新元素添加到堆栈中时，它将放置在顶部(或前面)而不是后面。 当我们想从堆栈中删除一个项目时，我们将从最上面的项目弹出。 因为新元素总是放在最前面，所以当我们需要删除某些东西时，总是会首先弹出那些新元素。 可以用缩写词LIFO记住这一点：后进先出。

For this algorithm, assume we have one temporary stack to hold the operators (we’ll call it “operator stack”) and one queue that will hold the final result.

对于此算法，假设我们有一个临时堆栈来保存运算符(我们将其称为“运算符堆栈”)，并且有一个队列将保存最终结果。

这个怎么运作 (How It Works)

The Shunting Yard Algorithm follows four basic steps:

调车场算法遵循四个基本步骤：

1. Parse the expression from left to right.
   从左到右解析表达式。
2. If we see an operand, output it to the results queue immediately.
   如果我们看到一个操作数，请立即将其输出到结果队列。

3. If we see an operator:

   如果我们看到运算符：

   a. If the operator stack is empty, push the incoming operator onto the operator stack.

   一个。 如果操作员堆栈为空，则将传入的操作员推到操作员堆栈上。

   b. If the incoming operator has higher precedence than what’s currently at top of the operator stack, push the incoming operator onto the top of the stack.

   b。 如果传入的运算符的优先级高于当前运算符堆栈顶部的优先级，则将传入的运算符推入堆栈的顶部。

   c. If the incoming operator has equal precendence, pop the top operator from the stack, output it to the queue, and push the incoming operator onto the stack.

   C。 如果传入的运算符具有相同的优先级，请从堆栈中弹出顶部运算符，将其输出到队列，然后将传入的运算符压入堆栈。

   d. If the incoming operator has lower precedence pop the top operator from the stack, output it to the queue, and test the incoming operator with the new top of the stack.

   d。 如果传入运算符的优先级较低，则从堆栈中弹出顶部运算符，将其输出到队列，然后使用堆栈的新顶部测试传入运算符。

4. Once we have parsed the whole expression, pop all remaining tokens from the operator stack.

   解析完整个表达式后，从运算符堆栈中弹出所有剩余的标记。

用调车场算法评估我们的表情 (Evaluating Our Expression with the Shunting Yard Algorithm)

It’s hard to make sense of those steps without seeing it in action, so let’s walk through our previous example and try to format it with the algorithm!

如果不看这些步骤就很难理解这些步骤，因此让我们来看一下前面的示例，并尝试使用算法对其进行格式化！

Convert this equation from infix notation to postfix notation: 5 + 10 * 3

将此方程式从中缀符号转换为后缀符号： 5 + 10 * 3

Let’s set up our two arrays: one for the results output and one for the temporary operator stack.

让我们设置两个数组：一个用于结果输出，另一个用于临时运算符堆栈。

expression = 5 + 10 * 3
    output = []
    operator stack = []

First we start reading our expression from left to right. So first up we have 5. Since this is an operand, we can output it immediately.

首先，我们开始从左到右阅读表达式。 所以首先我们有5 。 由于这是一个操作数，因此我们可以立即将其输出。

expression = + 10 * 3
    output = [5]
    operator stack = []

Next we see the +. The operator stack is empty, so we can just push it there

接下来，我们看到+ 。 操作员堆栈为空，因此我们可以将其推入此处

expression = 10 * 3
    output = [5]
    operator stack = [+]

Next up is 10, so we’ll output immediately.

接下来是10 ，所以我们将立即输出。

expression = * 3
    output = [5, 10]
    operator stack = [+]

Now we hit another operator, *. Since the operator stack isn’t empty, we have to compare it to the current top of the operator stack to see which has higher precedence.

现在我们碰到另一个运算符* 。 由于运算符堆栈不为空，因此我们必须将其与运算符堆栈的当前顶部进行比较，以查看哪个优先级更高。

If we look above, we see the current top of the stack is +. So comparing the two, we know multiplication has higher precedence than addition.

如果我们看上面，我们会看到当前栈顶为+ 。 因此，比较两者，我们知道乘法的优先级高于加法。

This means we can just push it onto the top of the stack, which gives us:

这意味着我们可以将其推入堆栈的顶部，从而获得：

expression = 3
    output = [5, 10]
    operator stack = [*, +]

Now we hit our final value, 3. Since this isn’t an operator, we can just output it immediately.

现在我们达到了最终值3 。 由于这不是运算符，因此我们可以立即将其输出。

expression is now empty
    output = [5, 10, 3]
    operator stack = [*, +]

Since the expression is now empty, all we need to do is pop all tokens from the operator stack and output them immediately. When we pop from the stack, we’re grabbing from the top, so first we’ll take the * to push to the end of the queue and then we’ll take the +.

由于表达式现在为空，因此我们要做的就是从运算符堆栈中弹出所有标记并立即输出它们。 当我们从堆栈中弹出时，我们从顶部开始抓取，因此我们首先将*推到队列的末尾，然后再使用+ 。

output = [5, 10, 3, *, +]

And that’s it! As you can see, it matches the above method where we just add parentheses, but this way is much easier for a computer to do.

就是这样！ 如您所见，它与上面添加括号的上述方法匹配，但是这种方式对于计算机而言要容易得多。

优先规则 (Precedence Rules)

You may have noticed there was one point where instead of using the algorithm to decide, we relied on our own knowledge to make a choice between what to do next: determining which operator had higher precedence.

您可能已经注意到，有一点不是使用算法来决定，而是依靠我们自己的知识在下一步操作之间做出选择：确定哪个运算符具有更高的优先级。

It’s not important right now while you understand the concepts behind the algorithm, but when we’re writing the actual code to solve this, we’re going to have to build in some precedence rules.

当您了解算法背后的概念时，现在并不重要，但是当我们编写实际代码来解决此问题时，我们将必须构建一些优先规则。

All we have to do is create an object that will essentially rank each operator. We’ll give the multiplication and division operators a rank of 2 and the addition and subtraction operators a rank of 1.

我们要做的就是创建一个对象，该对象将实质上对每个运算符进行排名。 我们将把乘除运算符的等级设为2，将加减运算符的等级设为1。

When we code it up, we’ll just compare two operators by comparing their numerical rank. The actual numbers 1 and 2 here are arbitrary, so don’t get too caught up in that. Just know that multiplication ranks higher than addition, so it has a higher number.

当我们对它进行编码时，我们将通过比较两个运算符的数值等级来比较它们。 这里的实际数字1和2是任意的，因此不要太着迷。 只是知道乘法的等级高于加法，所以它的数值更高。

const precedence = { "*":2, "/":2, "+":1, "-":1 };

评估我们的后缀表达式 (Evaluating our Postfix Expression)

We finally have our expression in Postfix Notation. Now we can use this format to evaluate it.

我们终于在Postfix Notation中有了表达式。 现在我们可以使用这种格式进行评估。

评估表达的算法 (Algorithm to Evaluate Our Expression)

Here’s how we’ll do it:

这是我们的处理方式：

1. Start with an empty stack.
   从一个空堆栈开始。
2. Parse the first token in the expression.
   解析表达式中的第一个标记。
3. If it’s an operand, push it onto the stack.
   如果是操作数，则将其压入堆栈。
4. If it’s an operator, pop off the appropriate number of operands from the stack into temporary variables. (For example, multiplication is a binary operator, so if you are parsing and you hit a multiplication operator, then you know to pop off two operands.)
   如果是运算符，请从堆栈中弹出适当数量的操作数到临时变量中。 (例如，乘法是一个二进制运算符，因此，如果您在解析时碰到了一个乘法运算符，则知道会弹出两个操作数。)
5. Evaluate that expression using the current operator and the two operands that were popped.
   使用当前运算符和弹出的两个操作数评估该表达式。
6. Push that result to the top of the stack.
   将结果推到堆栈的顶部。
7. Repeat 2-7 until the expression is empty.
   重复2-7，直到表达式为空。

In our example, we’re only dealing with binary operators, so we can just always pop off two operands when we see an operator. If we wanted to expand our example to handle all operators, we’d have to handle unary operators such as !.

在我们的示例中，我们只处理二进制运算符，因此我们总是可以在看到一个运算符时弹出两个操作数。 如果要扩展示例以处理所有运算符，则必须处理一元运算符，如! 。

遍历算法 (Walking Through the Algorithm)

Let’s walk through some pseudo-code where we use the algorithm to evaluate the above postfix notation expression: 5 10 3 * +.

让我们来看一些伪代码，在伪代码中我们使用算法来评估上述后缀表示法表达式： 5 10 3 * + 。

First we start by pushing every operand onto the stack until we hit an operator.

首先，我们首先将每个操作数压入堆栈，直到遇到运算符为止。

expression = [5, 10, 3, *, +]

    - push 5
    - push 10
    - push 3

    stack = [3, 10, 5]

So now we get to our first operator, *, which means it’s time to start popping. We pop until we have two values.

现在，我们进入第一个运算符* ，这意味着该开始弹出了。 我们弹出直到有两个值。

- pop 3
    - pop 10

Alright now we have our two operands, 3 and 10, so we will combine this with our operator, *, leaving us with 10 * 3.

好了，我们有两个操作数3和10 ，因此我们将其与运算符*结合在一起，剩下10 * 3 。

expression = [+]
    stack = [5]

    tempOperand1 = 3
    tempOperand2 = 10

    tempOperator = *

    eval(tempOperand1 + tempOperator + tempOperand2) // 3 * 10

We evaluate that, get 30, and then push this back onto the stack. We now have the following:

我们求值，得到30 ，然后将其推回堆栈。 现在，我们有以下内容：

expression = [+]
    stack = [30, 5]

So we start parsing the expression again and we immediately hit an operator. Again, we have to pop from the stack until we have two operands.

因此，我们再次开始解析表达式，然后立即点击运算符。 同样，我们必须从堆栈中弹出，直到有两个操作数。

expression = []
    stack = []

    tempOperand1 = 30
    tempOperand2 = 5

    tempOperator = + 

    eval(tempOperand1 + tempOperator + tempOperand2) // 30 + 5

We pop 30 and the 5 and we are ready to evaluate again. 5 + 30 gives us 35 and we can now push this back onto the stack.

我们弹出30和5 ，我们准备再次进行评估。 5 + 30给我们35 ，我们现在可以将其推回堆栈。

Going back to our original expression to parse for the next token, we find that it’s empty!

回到我们的原始表达式以分析下一个标记，我们发现它是空的！

expression = []
    stack = [35]

This either means that we are done or that the original expression was malformed.

这意味着我们完成了操作，或者原始表达格式不正确。

Let’s check by looking at our stack. Thankfully it only has one value in it, so this means we are done and 35 is the final output of the original expression, 5 + 10 * 3.

让我们通过查看堆栈进行检查。 幸运的是，它只有一个值，所以这意味着我们完成了 ， 35是原始表达式的最终输出5 + 10 * 3 。

前缀符号 (Prefix Notation)

The algorithm for evaluating an expression in prefix notation is essentially the same as above, except this time you will read from right to left. All we need is a small modification to the code and we can also evaluate for prefix notation.

用前缀表示法评估表达式的算法与上面的基本相同，只是这次您将从右至左阅读。 我们所需要做的只是对代码进行少量修改，并且我们还可以评估前缀符号。

If we go back to our original method of adding parentheses and moving operators, we can convert to prefix notation in the same way we did postfix. Instead of moving the operators to the end of their operands, we’ll move them to the beginning. Once we’ve done that, we can drop the parentheses altogether and then we have our prefix notation expression!

如果我们回到添加括号和移动运算符的原始方法，则可以像处理后缀一样转换为前缀表示法。 与其将运算符移到其操作数的末尾，不如将它们移至开始。 完成此操作后，我们可以完全删除括号，然后获得前缀表示法表达式！

5 + 10 * 3
    (5 + (10 * 3))
    (+ 5 (* 10 3))
    + 5 * 10 3

If you want to put your knowledge to the test, try to figure out how you’d do this algorithmically with a small modification to the shunting yard algorithm.

如果您想将自己的知识用于测试，请尝试通过对调车场算法进行少量修改来弄清楚如何在算法上进行此操作。

结论 (Conclusion)

In this tutorial, you’ve created an algorithm for converting expressions to postfix notation and tested it by evaluating an expression.

在本教程中，您创建了一种将表达式转换为后缀表示法的算法，并通过评估表达式对其进行了测试。

翻译自: https://www.digitalocean.com/community/conceptual_articles/understanding-order-of-operations