引言

作为一个程序员,你可能习惯于告诉计算机该做什么。 输入一些代码,运行它,计算机就可以执行你给它的任何命令。

尽管我们对计算机有着强大的控制力,但是在我们的代码中仍然有很多我们容易忽视的魔法在不断发生。 如果您使用具有预先构建函数的高级语言(就像我们大多数人一样) ,那么这一点尤其正确。 当然,虽然没有真正的理由去重新发明轮子,或者尝试自己实现这些有用的功能,但是看看引擎盖下面发生了什么还是很有趣的!

今天,我们将仔细研究这些看似显而易见的概念中的一个,我们可能都曾在某个时刻使用过: 操作的顺序。

假设你想计算这个表达式: 5 + 10 * 3。 根据运算的数学顺序,你应该先把10乘以3,然后再把乘积加5,但是你究竟要怎样告诉计算机去做这件事呢?

我们可以用几种不同的方式来解析这个等式,但是有些方式需要更多的背景知识。

在本教程中,您将看到如何着手解决这个问题。

这种方法要求我们首先将方程式转换成正确的格式。 一旦它变成了机器可读的形式,我们就可以继续通过解析算法提供它,这个算法将实际计算它。

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

中缀到后缀

尽管您可能还没有意识到这一点,但是大多数人可能已经熟悉了中缀符号。 上面的表达式,5 + 10 * 3,是用中缀符号写的。 这只是意味着操作符位于它们所执行的操作对象之间。

什么是逆波兰表示法?

如前所述,我们需要将方程式转换成计算机能够容易理解的格式。 这种形式被称为逆波兰表示法。

用逆波兰表示法表达式编写的表达式中,所有操作符都跟在操作数后面。

这一点非常重要,因为当机器读取这种格式的表达式时,它在执行操作数之前绝不会遇到操作符,这意味着它不必来回操作。

所以在前面的例子中,5 + 10 * 3变成5103 * + 。

这可能看起来不寻常,但是有一个方法论可以得出这个结论。

从 Infix 到 Postfix,人性化的转变之路

  1. 在优先顺序中加上括号
    (5 + (10 * 3))
  1. 将每个操作符移动到右边,直接放在它的结束括号之前
    (5 ( 10 3 *)+)
  1. 现在把括号全部去掉,这样我们就只剩下逆波兰表示法的表达式了
    5 10 3 * +

另一个例子,只是为了说明运算符不一定总是在最后:

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

再次强调,这对于计算机来说并不理想。 它仍然不知道把括号放在哪里。 幸运的是,我们有一个算法可以得到同样的结果。

调车场算法

调车场算法是 Dijkstra 开发的,用于将中缀表示法转换为逆波兰表示法表示法。

在进一步讨论之前,让我们先快速回顾一下这里要使用的两种数据结构: 堆栈和队列。 我们可以使用一个数组来保存这两组数据。 主要的区别在于我们添加和删除数据的顺序。

Queue ーー当我们向队列中添加数据时,我们将其推到后面。 想象一下,你正在排队参加一个活动,队伍中的每个人都是队列中的一个元素。 当您走到线路前时,您将自动插入到线路的后面。 当事件开始允许人们进入(从队列中移除元素)时,他们从队列的前面拉出,因为这些人在那里的时间更长。 你可以记住这个首字母缩写 FIFO: 先进先出。

堆栈——每次我们向堆栈中添加一个新元素时,它都会被放在堆栈的顶部(或前面) ,而不是后面。 当我们想要从堆栈中移除一个项目时,我们会弹出顶部的项目。 因为新元素总是放在最上面,所以当我们需要删除某些内容时,这些新元素总是会首先弹出。 这可以用首字母缩略词 LIFO 来记住: last in,first out。

对于这个算法,假设我们有一个临时堆栈来容纳运算符(我们称之为“运算符堆栈”)和一个将容纳最终结果的队列。

它是如何工作的

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

  1. 从左到右解析表达式。
  2. 如果我们看到一个操作数,立即将其输出到结果队列。
  3. 如果我们看到一个操作符: a。 如果操作符堆栈为空,则将输入的操作符推入操作符堆栈。 B. 如果输入运算符的优先级高于当前在运算符堆栈顶部的优先级,则将输入运算符推到堆栈顶部。 C. 如果输入操作符具有相同的精度,则从堆栈中弹出 top 操作符,将其输出到队列中,并将输入操作符推送到堆栈上。 D. 如果输入操作符的优先级较低,则从堆栈中弹出 top 操作符,将其输出到队列中,并用新的堆栈顶测试输入操作符。
  4. 解析完整个表达式后,从操作符堆栈中弹出所有剩余的标记。

用调车场算法求解表达式

如果没有看到这些步骤的实际应用,那么很难理解这些步骤,因此让我们回顾一下前面的示例,并尝试使用算法格式化它!

将这个等式从中缀表示法转换为逆波兰表示法: 5 + 10 * 3

让我们设置两个数组: 一个用于结果输出,另一个用于临时操作符堆栈。

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

首先,我们从左到右阅读表达式。 首先我们有5个。 由于这是一个操作数,我们可以立即输出它。

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

接下来我们看到的是 + ,操作符堆栈是空的,所以我们可以把它推到那里

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

下一步是10,所以我们将立即输出。

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

现在我们遇到另一个操作员,* 。 由于操作符堆栈不是空的,我们必须将其与当前操作符堆栈的顶部进行比较,以查看哪个优先级更高。

如果我们看上面,我们看到当前堆栈的顶部是 + 。 所以比较两者,我们知道乘法比加法有更高的优先级。

这意味着我们可以把它推到堆栈的顶部,这样就可以得到:

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

现在我们达到最终值3,因为这不是一个运算符,我们可以立即输出它。

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

因为表达式现在是空的,所以我们需要做的就是从操作符堆栈中弹出所有标记并立即输出它们。 当我们从堆栈中弹出时,我们是从顶部抓取,所以首先我们将 * 推到队列的末尾,然后我们将 + 。

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

就是这样! 正如您可以看到的,它与上面的方法相匹配,我们只需要添加括号,但是这种方法对于计算机来说要容易得多。

优先规则

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

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

我们所要做的就是创建一个对象,对每个操作符进行排序。 我们将给乘除运算符一个2的秩,给加减运算符一个1的秩。

当我们编写代码的时候,我们只是通过比较两个运算符的数值等级来比较它们。 这里的实际数字1和2是任意的,所以不要过于纠结于此。 只要知道乘法的等级比加法高,所以它有一个更高的数。

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

计算后缀表达式

我们终于有了逆波兰表示法表达式,现在我们可以使用这种格式来计算它。

计算我们表达式的算法

下面是我们将要做的:

  1. 从一个空的堆栈开始。
  2. 解析表达式中的第一个标记。
  3. 如果它是一个操作数,将它推到堆栈上。
  4. 如果是操作符,则从堆栈中弹出适当数量的操作数到临时变量中。 (例如,乘法是一个二进制运算符,所以如果在解析时遇到一个乘法运算符,就会弹出两个操作数。)
  5. 使用当前运算符和弹出的两个操作数计算该表达式。
  6. 将该结果推送到堆栈顶部。
  7. 重复2-7,直到表达式为空。

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

走遍算法

让我们来看看一些伪代码,在这些代码中,我们使用算法来计算上面的逆波兰表示法 / 值表达式: 5103 * + 。

首先,我们将每个操作数推到堆栈上,直到碰到一个操作符。

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

    - push 5
    - push 10
    - push 3

    stack = [3, 10, 5]

现在我们来看看第一个操作符 * ,这意味着是时候开始机械舞了。 我们弹出,直到我们有两个值。

    - pop 3
    - pop 10

现在我们有两个操作数,3和10,我们把它和操作符 * 结合起来,剩下10 * 3。

    expression = [+]
    stack = [5]

    tempOperand1 = 3
    tempOperand2 = 10

    tempOperator = *

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

我们对其进行评估,得到30,然后将其推回堆栈:

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

所以我们再次开始解析表达式,然后我们立即碰到一个操作符。 同样,我们必须从堆栈中弹出,直到有两个操作数。

    expression = []
    stack = []

    tempOperand1 = 30
    tempOperand2 = 5

    tempOperator = + 

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

我们得到了30和5,我们准备再次评估。 5 + 30等于35,现在我们可以把它推回堆栈。

回到我们的原始表达式来解析下一个令牌,我们发现它是空的!


    expression = []
    stack = [35]

这要么意味着我们完成了,要么意味着最初的表达式是畸形的。

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

前缀表示法

用前缀表示法计算表达式的算法基本上与上面相同,只是这次您将从右向左读取。 我们所需要的只是对代码进行一个小小的修改,并且我们还可以计算前缀符号。

如果我们回到最初添加括号和移动运算符的方法,我们可以像后缀一样转换为前缀符号。 我们不把操作符移到操作数的结尾,而是把它们移到开头。 一旦我们做到了这一点,我们可以删除括号,然后我们有我们的前缀符号表达式!

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

如果你想测试你的知识,尝试找出你会如何做这个算法与一个小修改调车场算法。

总结

在本教程中,您已经创建了一个将表达式转换为逆波兰表示法的算法,并通过计算表达式对其进行了测试。