抽象数据类型 c数据类型的问题 ■抽象数据类型 1.在同一个程序中,如果栈的 ■实质为“逻辑结构+运算/操作 隐蔽了存储实现细 StackElementType不同 上层算法以一致的形式调用底层数据结构 需要定义不同的栈 例如在STLC++中 2.从顺序栈改为链式栈 Stack push(x) 顺序找,链式找 上层调用语句一定要改变 上层调用语句不需要改变 真太血张写 大血张體 新有食究 253栈的应用-计算表达式的值 计算表达式的值 栈可以应用于递归函数 ■表达式的递归定义 ( recursive function)的实现 ■基本符号集:{0,1,…,9,+,一 ■使用下推表(栈)自动进行复杂 的算术表达式的递归求值 因子《常数李{项>, 后缀表达式 CK ■后缀表达式求值 bacK 真太张铭写 北盒大管血歌张写 新究 语法公式(中缀表达法) 后缀表达式 BNF范式,可以利用Lex,Yacc等自动构造编译器 <表达式>=<项〉<项〉 项 ■表达式》∷=〈项〉+<项〉|〈项〉一〈项〉 <项〉 送分>1因于 <因子》*<因子〉|<因子>/< 因子〉<因子〉*|<因 子〉<因子〉/〈因子 ■<因子〉::=<常数〉 因子 <常数〉 ■<常数>=<数字>|<数字><常数 ■〈数字>》:=0|1|2|3|4|5|6|7 <常数>∷=<数字>|<数字><常数〉 数字〉.<常数 数字》:=0|1|2|3|4|5|6 back 真大带酱张储 新有,种究 北大管息歌张帖习9 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 49 back next 抽象数据类型 „ 抽象数据类型 „ 实质为“逻辑结构 + 运算/操作” „ 隐蔽了存储实现细节 „ 上层算法以一致的形式调用底层数据结构 „ 例如在STL C++中 „ Stack.push(x) „ 顺序栈，链式栈 „ 上层调用语句不需要改变 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 50 back next C数据类型的问题 „ 1. 在同一个程序中，如果栈的 StackElementType 不同 „ 需要定义不同的栈； „ 2. 从顺序栈改为链式栈 „ 上层调用语句一定要改变 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 51 back next 2.5.3 栈的应用--计算表达式的值 „ 栈可以应用于递归函数 (recursive function)的实现 „ 使用下推表（栈）自动进行复杂 的算术表达式的递归求值 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 52 back next 计算表达式的值 „ 表达式的递归定义 „ 基本符号集：{0，1，…，9，+，-， *，/，（，）} „ 语法成分集：{ <表达式> , <项> , <因子> , <常数> , <数字> } „ 语法公式集 „ 后缀表达式 „ 后缀表达式求值 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 53 back next 语法公式(中缀表达法) BNF范式，可以利用Lex,Yacc等自动构造编译器 „ <表达式>∷= <项> + <项> | <项> － <项> | <项> „ <项> ：：= <因子> * <因子> |<因子> / < 因子> |<因子> „ <因子> ::= <常数> | （ <表达式> ） „ <常数>∷= <数字> |<数字> <常数> „ <数字>∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 54 back next 后缀表达式 „ <表达式>∷= <项> <项> + | <项 > <项> － | <项> „ <项> ：：= <因子> <因子> * | <因 子> <因子> / | <因子> „ <因子> ::= <常数> „ <常数>∷= <数字> | <数字> <常数> | <数字> . <常数> | „ <数字>∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9