04-3 第4章 树3.pptx

第83页：练习

练习：构造后缀表达式ab+cde+*-f-gh+*对应的二叉树

第84页：后缀表达式求值的方法

842、后缀表达式求值的方法：若已知后缀表达式，从左到右读入后缀表达式的各个符号，①若读到的是操作数，将它压入堆栈。②若读到的是运算符，就从栈中连续弹出两个元素，进行相应的运算，并将结果压入栈。③读入结束符时，栈顶元素就是计算结果。

第85页：操作后缀表达式栈

• 操作后缀表达式栈T2=A/T1T2DE*+AC*-=
• T2DET3=D*E T2T3+AC*-=
• T2T3T4=T2+T3T4AC*-=
• T4ACT5=A*C T4T5-=
• T4T5T6=T4-T5 =
• T6T1=B*C AT1/DE*+AC*-=
• AT1——ABC*/DE*+AC*-=
• ABC[例]计算后缀表达式ABC*/DE*+AC*-

第86页：表达式树的基础上

在表达式树的基础上，通过后根遍历，可以计算表达式的值：当访问一个叶结点时，把对应的值压入堆栈中；当访问一个非叶结点时，从堆栈中连续弹出两个值，按此结点规定的操作进行运算，并且结果压回到堆栈中；当遍历终止时，堆栈中只有一个值，它就是表达式的值。

第87页：算法GetValue

算法GetValue(t.value)GetValue1. [创建辅助堆栈，根指针入栈]IFt= THEN RETURN.CREATE (S).CREATE (calculator).S←(t, 0) .

第88页：后根遍历二叉树

GetValue2.[后根遍历二叉树，并计算表达式值]WHILES非空DO((t,i)←SIFi=0THEN(S←(t,1).IFLeft(t)≠ THENS←(Left(t),0)).)IFi=1THEN(S←(t,2).IFRight(t)≠ THENS←(Right(t),0)).)IFi=2THEN(IFLeft(t)= ANDRight(t)= THENcaculator←Data(t).ELSE(operand2←caculator.operand1←caculator.op←Data(t).IFop="+"THEN(result←operand1+operand2.)IFop="−"THEN(result←operand1−operand2.)IFop="×"THEN(result←operand1×operand2.)IFop=""THENIFoperand2≠0THENresult←operand1operand2.caculator←result.)))

第89页：变量赋值

GetValue3. [为value变量赋值]value←caculator.▐

第90页：中缀表达式转换成后缀表达式设定一个堆栈

903、中缀表达式转换成后缀表达式设定一个堆栈，用来保存扫描中缀表达式得到的暂不能放入后缀表达式中的符号。基本思想：从左到右依次读中缀表达式的各个符号，并根据如下规则进行处理：1.假如是操作数，将其放入后缀表达式中；2.如果是运算符，则：（1）栈空或栈顶不是运算符：运算符入栈（2）栈顶为运算符：比较当前读到的运算符与栈顶运算符的优先级

第91页：读出的运算符

911）若读出的运算符的优先级大于栈顶运算符的优先级，则将其压入运算符栈；2）若读出的运算符的优先级小于等于栈顶运算符的优先级，弹出栈顶运算符放入后缀表达式中，返回2继续比较；3.遇到“（”，压入堆栈；4.遇到“）”，把“（”上面的运算符依次弹出加到后缀表达式中，“（”出栈；5.如果读出的是表达式结束符“#”，栈中剩余的运算符依次出栈，并写到后缀表达式中，转换完成。

第92页：栈输出序列

92(A+B)*((C-D)*E+F)栈输出序列（A（＋A BA B＋*(( A B＋C*((-A B＋CD*( A B＋CD-*(* A B＋CD-E*(＋A B＋CD-E**(＋A B＋CD-E*F* A B＋CD-E*F+A B＋CD-E*F+ *

第93页：课后作业

课后作业130页4-10、4-12