程序设计导论：Python语言实践

4.3.4　堆栈的应用

下堆栈在计算中起着至关重要的作用。如果你学习了操作系统、程序设计语言或其他计算机科学中的高级课题，你将了解到栈不仅可以直接应用于许多应用程序，而且还可以作为执行高级程序设计语言（例如Python）编写的程序的基础。

1. 算术表达式

在第1章讨论的一些初级程序中包含计算算术表达式的值，例如：

也就是说，4乘以5，3加上2，然后将结果相乘，再加上1，最后得到结果101。但是，Python如何执行这种计算呢？无需详细讨论Python的构建原理，我们可以讨论其基本思想，通过编写一个程序，接收一个字符串作为输入（表达式），然后输出表达式产生的值。为了简单起见，我们从如下显式递归定义开始：一个算术表达式要么是一个数值，要么是一个左括号跟随一个算术表达式，跟随一个运算符，跟随另一个算术表达式，跟随一个右括号。同样，为了简单起见，这个定义适用于全括号（fully parenthesized）算术表达式，精确指定哪个运算符应用于哪一个操作数。通过稍多的工作，我们还可以处理类似于1 + 2 * 3的表达式，方法是使用运算符优先级规则代替括号，但是我们没有考虑这种复杂性。为了简洁性，我们支持常用的二元运算符*、+和-，以及带一个参数的平方根运算符sqrt。我们可以很容易地扩展到更多的运算符和更多类型的运算符，以包括大量常用的数学表达式，包括三角函数、指数运算、对数函数和其他任何希望包括的运算符。然而，我们的重点是理解如何解释包含括号、运算符和数值的字符串，来实现以正确的运算优先级顺序执行所有计算机上都支持的低级算术运算。 ...