Macaulish

栈的应用：

１．表达式求值

EXP = S1 + OP + S2

则称 OP+S1 +S2为表达式的前缀表达式

 称 S1+OP+S2为表达式的中缀表达式

 称 S1+S2+OP 为表达式的后缀表达式

EXP = a*b+(c-d/e)*f

前缀表达式:+*ab*-cd/ef

中缀表达式:a*b+c-d/e*f

后缀表达式:ab*cde/-f*+

结论：

1） 操作数之间的相对次序不变

2） 运算符的相对次序不同

3） 中缀表达式失去了括号信息，致使运算的次序不确定

4） 前缀表达式的运算规则为：连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式

5） 后缀表达式的运算规则：运算符在式中出现的顺序恰为表达式的运算顺序，每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式

如何从一个表达式得到后缀式？

每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先级高的运算符领先于优先级低的运算符。

1） 设立运算符栈

2） 设表达式的结束符为“#”设运算符栈序为“#”

3） 若当前字符是操作数，则直接发送给后缀式

4） 若当前运算符的优先级高于栈顶运算符，则进栈

5） 否则，退出栈顶运算符发送给后缀式

6） “（”对它之前后的运算符起隔离作用，“）”可视为自相应左括号开始的表达式的结束符。

2． 函数递归

在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前需要完成三件事：

1） 将所有的实参、返回地址等信息传递给被调用函数保存

2） 为被调用函数的局部变量分配存储区

3） 将控制转移到被调用函数入口

在被调用函数返回调用函数之前应该完成

1） 保存被调用函数的计算结果

2） 释放被调用函数的数据区

3） 依照被调用函数保存的返回地址将控制转移到调用函数

多个函数嵌套调用的规则是：

后调用先返回此时的内存管理实行“栈式管理”

递归过程指向过程中占用的数据区称之为递归工作栈

每一层的递归参数合成一个记录称之为递归工作记录

栈顶记录指示当前层的执行情况称之为当前活动情况