调度场算法
标签: # Python # LeetCode # Dijkstra # 调度场算法 # 逆波兰表达式 # 算法

调度场算法由 Edsger W. Dijkstra 发明,用于将中缀表达式转换成后缀表达式,即逆波兰表达式。写过程序的同行都了解,对于计算机来说,一个后缀表达式更容易被理解和计算,所以当处理我们看起来更习惯的中缀表达式时,例如 (3 + 4) * 5 - 2 * (3 + 9) ,往往会将其转换成 3 4 + 5 * 2 3 9 + * - 的形式,这样只需要一个栈结构就能得出正确结果 11 ,代码简单到什么程度呢?只要稍微有些数据结构知识的码农,都可以很快写出类似下面的代码。 def calculate_reverse_polish_notation(tokens): stack = [] for token in tokens: if token == '+': stack.append(stack.pop() + stack.p