信息学奥赛知识点(十三)----树和二叉树(下)
一、表达式的求法
考试中有经常出现类似于“中缀表达式转后缀”，“前缀表达式转后缀”等。如果能画出唯一的二叉树那么便根据二叉树的结构之间求解即可，有些情况很难直接画出二叉树。还有通过加括号的方式进行求解，还有利用栈的方法求表达式。
(1) 【中缀转后缀：利用栈】
规则：①从左往右遇到操作数直接输出
②遇到操作符，放入栈中
③遇到左括号，入栈
④遇到右括号，出栈(直到遇到左括号，左括号只弹出不输出)
⑤遇到其他操作符，弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
⑥最终将栈中元素依次输出
【例题】：将a+b*c+(d*e+f)*g转换成后缀表达式
* | * | ||||||||
* | * | ( | ( | ( | ( | ||||
+ | + | + | + | + | + | + | + | + | + |
遇到a, ① 显示a | 遇到+, ② 显示a | 遇到b,① 显示ab | 遇到*,② 显示ab | 遇到c,① 显示abc | 遇到+,⑤ 显示abc*+ | 遇到(, ③ 显示abc*+ | 遇到d，① 显示abc*+d | 遇到*，② 显示abc*+d | 遇到e，① 显示abc*+de |
+ | + | ||||
( | ( | * | * | ||
+ | + | + | + | + | |
遇到+, ⑤ 显示 abc*+de* | 遇到f, ① 显示 abc*+de*f | 遇到)，④ 显示 abc*+de*f+ | 遇到*，② 显示 abc*+de*f+ | 遇到g,① | ⑥ 显示 abc*+de*f+g*+ |
【中缀转后缀：括号法】
① 根据运算符的优先级对中缀表达式加括号（有几个运算符就有几对括号）（原本有的括号不用加）
② 将运算符移到对应的括号后面
③ 去掉所有括号，即为后缀表达式
原式：a+b*c+(d*e+f)*g
根据优先级加括号过程
a+b*c+(d*e)+f*g
a+b*c+((d*e)+f)*g
a+(b*c)+((d*e)+f)*g)
(a+(b*c))+((d*e)+f)*g)
((a+(b*c))+((d*e)+f)*g))
将每组括号中的运算符移到括号右侧：
((a+(b*c))+((d*e)+f)*g))
((a+(b*c))+((de)*+f)*g))
((a+(b*c))+((de)*f)+*g))
((a+(bc)*)+((de)*f)+g)*)
((a(bc)*)++((de)*f)+g)*)
((a(bc)*)+((de)*f)+g)*)+
(1) 【后缀转中缀：利用栈】
规则：①从左往右，遇到数就入栈，
②遇到操作符就出栈两个数（栈底元素 + 操作符 +栈顶元素 ），然后将两个数入栈。
【例题】将表达式24 8 + 3 * 4 10 7 - * / 转换为中缀表达式
7 | |||||||||
10 | 10 | 10-7 | |||||||
8 | 3 | 4 | 4 | 4 | 4 | 4*(10-7) | |||
24 | 24 | (24+8) | (24+8) | (24+8)*3 | (24+8)*3 | (24+8)*3 | (24+8)*3 | (24+8)*3 | (24+8)*3 |
遇到24，① | 遇到8，① | 遇到+,② | 遇到3,① | 遇到*,② | 遇到4，① | 遇到10,① | 遇到7，① | 遇到-,② | 遇到*,② |
(24+8)*3/(4*(10-7)) |
遇到/，② |
【后缀转中缀：括号法】
过程：
从前往后，看到符号就把左侧的两个表达式加上括号，变成新的表达式。
24 8 + 3 * 4 10 7 - * /
(24 8 +) 3 * 4 10 7 - * /
((24 8 +) 3 * ) 4 10 7 - * /
((24 8 +) 3 * ) 4 (10 7 -) * /
((24 8 +) 3 * ) (4 (10 7 -) *) /
(((24 8 +) 3 * ) (4 (10 7 -) *) /)
将运算符加在括号内运算数中间：
(((24+8) 3 * ) (4 (10 7 -) *) /)
(((24+8) * 3 ) (4 (10 7 -) *) /)
(((24+8) * 3 ) (4 (10 - 7) *) /)
(((24+8) * 3 ) (4 * (10 - 7) ) /)
(((24+8) * 3 ) / (4 * (10 - 7) ) )
一层一层去掉括号，不影响原来的运算顺序
((24+8) * 3 ) / (4 * (10 - 7) )
(24+8) * 3 / (4 * (10 - 7) )
(1) 【前缀转中缀：利用栈】
规则：①从右往左，遇到数就入栈，
②遇到操作符就出栈两个数（栈顶元素 + 操作符 +栈底元素 ），然后将表达式入栈。
【例题】将前缀表达式 - * + 3 4 5 6 转换成中缀表达式
3 | ||||||
4 | 4 | 3+4 | ||||
5 | 5 | 5 | 5 | (3+4)*5 | ||
6 | 6 | 6 | 6 | 6 | 6 | (3+4)*5-6 |
遇到6，① | 遇到5，① | 遇到4,① | 遇到3,① | 遇到+,② | 遇到*，② | 遇到-,② |
【前缀转中缀：括号法】
过程：
从右往左，看到符号就把右侧的两个表达式加上括号，变成新的表达式。
- * + 3 4 5 6
- * (+ 3 4) 5 6
- (*(+ 3 4) 5) 6
(- (* ( + 3 4 ) 5 ) 6)
将运算符加在括号内运算数中间：
(- (* ( 3 + 4 ) 5 ) 6)
(- ( ( 3 + 4 ) *5 ) 6)
(( ( 3 + 4 ) *5 ) -6)
一层一层去掉括号，不影响原来的运算顺序
(( ( 3 + 4 ) *5 ) -6)
( ( 3 + 4 ) *5 ) -6
( 3 + 4 ) *5 -6
(1) 【中缀转前缀：利用栈】
规则：①从右往左遇到操作数直接输出
②遇到操作符，放入栈中
③遇到右括号，入栈
④遇到左括号，出栈(直到遇到右括号，右括号只弹出不输出)
⑤遇到其他操作符，弹出所有优先级大于该运算符的栈顶元素，然后将该运算符入栈
⑥最终将栈中元素依次输出。
⑦最后将表达式反转。
【例题】将中缀表达式5+10*(2+6)-8转换成前缀表达式
+ | + | ||||||||
) | ） | ） | ) | * | * | + | |||
- | - | - | - | - | - | - | - | - | |
遇到8，① 显示8 | 遇到-，② 显示8 | 遇到),③ 显示8 | 遇到6,① 显示8 6 | 遇到+,② 显示8 6 | 遇到2，① 8 6 2 | 遇到(,④ 显示8 6 2 + | 遇到*，⑤ 显示8 5 2+ | 遇到10，① 显示8 5 2 + 10 | 遇到+，⑤ 显示8 6 2 + 10 * |
+ | ||
- | ||
遇到5，① 显示8 6 2 + 10 * 5 | ⑥ 8 6 2 + 10 * 5 + - | ⑦ - +5*10+2 6 8 |
【中缀转前缀：括号法】
根据运算优先级，加括号
5+10*(2+6)-8
5+(10*(2+6))-8
(5+(10*(2+6)))-8
((5+(10*(2+6)))-8)
将运算符放到括号的前面
((5+(10*+(26)))-8)
((5+*(10+(26)))-8)
(+(5*(10+(26)))-8)
-(+(5*(10+(26)))8)
去掉括号
-+ 5* 10+2 6 8
(adsbygoogle = window.adsbygoogle || []).push({});