数据结构学习之路二计算机计算与栈

jiezi

5 年前

** 本博客内容根据 Mooc 浙江大学数据结构 2.2 课堆栈一课总结得到
如果对于博客中的算法有任何疑问请您斧正 **

当计算机面对一个复杂的算术表达式要如何进行计算呢？

首先如果是 3 + 2 这个简单的算术表达式, 我们可以从左到右将表达式分解成, 运算数 3，2 和运算符号 ”+”, 然后就可以轻松的得到结果也就是 5, 如果我们利用机器来计算，那么也会是同样的道理。但是我们知道运算符号是有优先级的，如果我们现在要计算的表达式是 2 + 3/2 这样的一个稍复杂的计算表达式的时候, 如果我们还是简单的从左到右进行分解 运算数 和运算符号 ，那么这其中就会多出很多复杂的计算判定。因此, 我们有了一个更利于计算的表达式 后缀表达式。

后缀表达式就是运算符号是在要运算的两个数之后。而上面两个我们在生活中常见的算数表达式也被称为 中缀表达式。我们将2 + 3/2 这个中缀表达式变成后缀表达式, 就会得232/+。第一次面对这个后缀表达式肯定会感觉很奇怪，但如果我们知道这个表达式是如何运作后，我们也将会知道为什么后缀表达式更适合计算机来计算。

对于 232/+这个后缀表达式。我们从左到右进行遍历，如果得到是 运算数 我们就找 ” 一个地方 ” 进行存储。

如果是 运算符 , 就去存储的地方找到后进入的两个 运算数, 然后进行计算, 接着把结果继续存储。

不断重复这个过程，直到循环结束，最终我们就会得到最后的结果。

下图 1.1 就表明了后缀表达式的运算过程
其中存储结构最上方为当前循环的运算数，存储结构中显示为此次循环后存储结构的结果:

                        图 1.1 后缀表达式的运算过程

我们可以看到我们利用了一个特殊的存储方式，先进入到存储结构的元素反而是最后从存储结构出来的，这种存储数据的结构也就是 栈。栈的特点就是先进后出, 每次从栈中推出的元素都是最后进入的元素。栈在计算机计算过程经常会变用到, 在我的理解当中当我们在计算过程中如果需要记录之前的结果并且在后面利用到它, 那么这个时候我们就都可以利用栈。例如我们常用的递归其实也是利用了栈来存储 ” 上一个结果 ” 的。

"""
  要实现一个最简单的栈，我们基本只要实现两个方法，一个是栈的 push 方法，把元素压入栈里面。另一个就是 pop 方法，把栈的最后一个元素推出并返回该元素
"""
class Stack:

  # 不要让类变量是可变对象
  # values = []

  def __init__(self):
      self.values = []

  def __getitem__(self, item):
      return self.values.__getitem__(item)

  def push(self, value):
      self.values.append(value)

  def pop(self):
      return self.values.pop()

  def __len__(self):
      return len(self.values)

首先我们还是循环中缀表达式, 这个时候我们不关心数字, 所以我们当我们遇到数字就直接输出这个数字。

而当我们遇到的是 运算符 的时候，我们就要先把这个运算符和栈里面已有的运算符进行比较，因为我们在计算的时候会先计算优先级高的运算符, 所以我们要把栈里面比当前循环到的运算符优先级高的运算符输出, 然后把当前的这个运算符压栈。

当然有一个特殊的运算符号也就是 ”()” 括号，这个时候我们就要特殊处理了，如果是 ”(“，我们直接入栈，如果遇到了 “)” 这个时候我们就要把栈里面 ”(“ 后面的所有运算符都出栈。最后如果循环结束，这时候我们就要把栈里面剩下的所有运算符都出栈

"""
只是简单实现 不考虑中缀表达式中的浮点数, 
并且只简单的处理 "*","/","+","-","(",")" 等符号
"""def convert_the_infix_expression_to_suffix_expression(infix_expression: str) -> list:"""
    :param infix_expression:
    :return:

    Usage::
        >>> convert_the_infix_expression_to_suffix_expression("3 + 2 / 4")
        [3, 2, 4, "/", "+"]
    """
    res = []
    operator_stack = Stack()

    # 存储符号的等级
    operator_ranks = {
        "*": 2,
        "/": 2,
        "+": 1,
        "-": 1,
        "(": 0,
        ")": 0
    }
    for operator in infix_expression:
        if operator.isdigit():
            # 数字直接存入
            res.append(int(operator))
        else:
            # 操作符要和 stack 里面的进行比较
            if operator == "(":
                operator_stack.push(operator)
            elif operator == ")":
                # 遇到右括号把栈里面(上的所有符号 pop 出来
                while operator_stack and operator_stack[-1] != "(":
                    res.append(operator_stack.pop())
                # 把 "(" 抛出
                operator_stack.pop()
            elif operator.isspace():
                continue
            else:
                # 把栈里面所有优先级 >= 当前运算符的都抛出
                # 然后把当前运算符加入
                while operator_stack and operator_ranks[operator_stack[-1]] >= operator_ranks[operator]:
                    res.append(operator_stack.pop())
                operator_stack.push(operator)
    #  把符号栈里面的所有符号抛出
    while operator_stack:
        res.append(operator_stack.pop())
    return res

通过上述的学习，我们也就可以了解到了 中缀表达式 , 后缀表达式 ， 栈，以及在面试当中会问到的中缀到后缀的转换。

Mooc- 数据结构

数据结构学习之路二计算机计算与栈

问题:

思考历程:

什么是后缀表达:

如何通过后缀表达式进行计算：

C1 python 中栈的简单实现:

如何把中缀表达式变成后缀表达式：

C2 python 中中缀表达式变后缀的简单实现:

总结：

参考