四、堆栈数据表示 含义:凡是按先进后出方式工作的特殊(存储)区 域称为堆栈。 2.堆栈组成方式 1)寄存器堆栈,全由寄存器构成,速度快,扩充栈容 成本高。 2)寄存器与存贮器结合堆栈 ①寄存器速度快作栈顶(需数个栈顶寄存器) ②存贮器价格低扩充栈容易 3.堆栈的生长方式 通常采用向下生长方式:压入数据后,堆栈指针SP向 地址减少方向变化
四、堆栈数据表示 1. 含义：凡是按先进后出方式工作的特殊（存储）区 域称为堆栈。 2. 堆栈组成方式： 1）寄存器堆栈，全由寄存器构成，速度快，扩充栈容 成本高。 2）寄存器与存贮器结合堆栈。 ①寄存器速度快作栈顶（需数个栈顶寄存器）。 ②存贮器价格低扩充栈容易。 3. 堆栈的生长方式 通常采用向下生长方式：压入数据后，堆栈指针SP向 地址减少方向变化
4.堆栈的主要作用 1)保护信息,保存现场; 2)支持子程序嵌套与中断嵌套以及递归调用的正确进 入与返回; 3)十分有利于完成对逆波兰表达式的运算。 5.逆波兰表达式及其运算 1)三种表达式 ①数学表达式:AB ②波兰表达式:+AB ③逆波兰表达式:AB+
4. 堆栈的主要作用 1）保护信息，保存现场； 2）支持子程序嵌套与中断嵌套以及递归调用的正确进 入与返回； 3）十分有利于完成对逆波兰表达式的运算。 5. 逆波兰表达式及其运算 1）三种表达式 ①数学表达式：A+B ②波兰表达式：+AB ③逆波兰表达式：AB+
2)数学表达式的树结构 ①把运算符做结点 ②把运算元素做叶子。 ③把最后一个运算符作根节点(二叉树) 例:(A+B)*C-D/(E+F)
* + / - + C B D A E F 2）数学表达式的树结构 ①把运算符做结点。 ②把运算元素做叶子。 ③ 把 最 后 一 个 运 算 符 作 根 节 点 （ 二叉树 ） 例：（A+B）*C-D/（E+F）
3)逆波兰表达式的生成 利用后序遍历树,生成逆波兰表达式要点: 先左,后右,先枝叶,后结点,依次收集运算元 素与运算符,直到最后一个运算符(根结点)为止 AB+C DEF+/- 4)在堆栈机上完成逆波兰表达式运算 要点:见运算元素压入堆栈 见运算符就将次栈顶元素与栈顶元素进行相应运算 结果留在栈顶,直到最后一个运算符
3）逆波兰表达式的生成 利用后序遍历树，生成逆波兰表达式要点： 先左，后右，先枝叶，后结点，依次收集运算元 素与运算符，直到最后一个运算符（根结点）为止。 AB+C*DEF+/- 4）在堆栈机上完成逆波兰表达式运算 要点：见运算元素压入堆栈。 见运算符就将次栈顶元素与栈顶元素进行相应运算， 结果留在栈顶，直到最后一个运算符
A B 3 4 (6 B顶[A+B顶[C (A+B)*C A次顶 A+B DMA ∧ 0)/ E+F EDMA FEDM D/(E+F)(A+B)*C-D/(E+F) D M A 6.利用堆栈机指令射道波兰表达式编程 (HP3000堆找机指令)
6 . 利 用 堆 栈 机 指 令 对 逆 波 兰 表 达 式 编 程 （HP3000堆栈机指令） A Λ （A+B）*C Λ C A+B Λ D M Λ A+B Λ B A Λ 1 2 3 + 4 C 5 * 6 D A B 顶 次顶 顶 E D M 7 E F E 8 F E+F D M 9 D/（E+F) M Λ 1 0 / （A+B）*C-D/（E+F) Λ 1 1 - Λ + D M Λ Λ