两个共享一个存储区 第三章栈和队列 status empty( dustktp s, int sno) i switch sno )i case 1: return(s top[0]=0)i breaki case 2: return(s top[1]= m+l)i break )//empty status full(dustktp s) return(s.t。p[0]+1>=s.t。P[1]) 注,过程 push stack中 if(s.top[0]+1=s,七。P[1])… 亦可改写成一 if( full(s)) 第26页
第三章 栈和队列 第26页 Status empty( dustktp s, int sno) { switch( sno ){ case 1: return(s.top[0] = 0); break; case 2: return(s.top[1] = m+1); break; } } //empty Status full(dustktp s) { return (s.top[0]+1 >= s.top[1]); } 注. 过程push_stack中 if( s.top[0]+1 = s.top[1] )…; 亦可改写成 if( full(s)) ···; ⚫ 两个栈共享一个存储区
第三章栈和队列 2、栈的型应用示例一一表达式求值 0表达式的传统标记法一二中级标记法 表达式的成分 操作数( Operand):常数或常数标识符、变量标识符、函数等 运算符( Operator):算术运算符、关系运算符、逻辑运算符等 界限符( Delimiter):左括号、右括号、表达式结束符等 表达式的分类 算术表达式:如b*b-4*a*c 关系表达式:如b*b-4*a半c>=0 布尔表达式:如(a<>0)AND(b*b-4*a*c>=0) 传统标记法一中缀标记法 舴点:运算符出现在操作数之间 第27页
第三章 栈和队列 第27页 表达式的成分 操作数(Operand)：常数或常数标识符、变量标识符、函数等 运算符(Operator)：算术运算符、关系运算符、逻辑运算符等 界限符(Delimiter)：左括号、右括号、表达式结束符等 表达式的分类 算术表达式：如 b*b - 4*a*c 关系表达式：如 b*b - 4*a*c >=0 布尔表达式：如 (a<>0) AND (b*b - 4*a*c>=0) 传统标记法——中缀标记法 特点：运算符出现在操作数之间 ⚫ 表达式的传统标记法——中缀标记法 2、栈的典型应用示例——表达式求值
第三章栈和队列 2、栈的型应用示例一一表达式求值 表达式的传纺标记法一中领标记法 示例计算8(3+2×6)5+4 8(3+2×6)/5+4 8-(3+12)/5+4 =8-15/5+4 =8-3+4 =5+4 9 第28页
第三章 栈和队列 第28页 示例 计算 8-(3+2×6)/5+4 8-(3+2×6)/5+4 = 8-(3+12)/5+4 =8-15/5+4 =8-3+4 =5+4 =9 ⚫ 表达式的传统标记法——中缀标记法 2、栈的典型应用示例——表达式求值
一单算术表达式求值算法一一算符优先算法一 第三章栈和队列 讨论简单算术表达式的求值问题 运算符:+,* 界限符(广算符op 算符优先法:根据算术四则运算的规则亦即运算优先关系 的规定,实现对表达式的编译或解释执行 使用檨实现简单算术表达式的求值运算。 依据算术四则运算的规则,在运算的每一步中。任何两个 相继出现的算符01和02之间的优先关系,可能是 01<020的优先数低于0 01=0201的优先数等于02 01>0201的优先数高于02 第29页
第三章 栈和队列 第29页 简单算术表达式求值算法——算符优先算法 讨论简单算术表达式的求值问题。 算符op 界限符 运算符 + − :(,), # : , , ,/ 算符优先法：根据算术四则运算的规则亦即运算优先关系 的规定，实现对表达式的编译或解释执行。 使用栈实现简单算术表达式的求值运算。 依据算术四则运算的规则，在运算的每一步中。任何两个 相继出现的算符θ1和θ2之间的优先关系，可能是 θ1<θ2 θ1的优先数低于θ2 θ1=θ2 θ1的优先数等于θ2 θ1>θ2 θ1的优先数高于θ2
简单算术表达式求值算法一算符优先算法 第三章栈和队列 # 算符的优先关系表 */ )>>> <> 说明: *和/"为01时的优先性均低于(,但高于”); 2)当01=02时,令01>0 3)(=)‘表示当左、右括号相遇时,括号内的运算已经完成; 4)'#"是表达式的结束符。设表达式的最左边也虚设一个#符,以 一构成整个表达式的一对“括号” 与‘#,)与(以及#与)之间无优先关系,若出现此类 情况,应是语法错误。下面的讨论中,假定不会出现语法错误 6)1#=1#'丰示整个表诂式求值完毕 第30页
第三章 栈和队列 第30页 算符间的优先关系表 说明： 1）‘+ ’ 、 ‘ - ’ 、 ' * '和' / '为θ1时的优先性均低于'(' ，但高于' ) ' ； 2）当θ1=θ2 时，令θ1>θ2 ; 3） '(' = ') '表示当左、右括号相遇时，括号内的运算已经完成； 4） ' # '是表达式的结束符。设表达式的最左边也虚设一个#符，以 构成整个表达式的一对“括号”， 5） ‘(’与‘ # ’ ， ') '与'('以及' # '与') '之间无优先关系，若出现此类 情况，应是语法错误。下面的讨论中，假定不会出现语法错误 ； 6） ' # ' = ' # '表示整个表达式求值完毕。 简单算术表达式求值算法——算符优先算法 θ2 θ1 + - * / ( ) # + > > < < < > > - > > < < < > > * > > > > < > > / > > > > < > > ( < < < < < = ) > > > > > > # < < < < < =