中缀式转换为前缀式以及后缀式
- 假设中缀表达式为:
a+b*c-(d+e)
- 第一步:根据运算符的优先级对所有运算单位加括号 式子变为:
((a+(b*c))-(d+e))
- 转换为前缀: 把运算符号移动到对应的括号的前面
- 式子变为:
-(+(a*(bc))+(de))
=======================把括号去掉 - 前缀表达式:
-+a*bc+de
- 转换为后缀: 把运算符号移动到对应的括号的后面
- 式子变为:
((a(bc)*)+(de)+)-
- =======================把括号去掉
后缀表达式:abc*+de+-
总结:前缀式和后缀式是不需要用括号来进行优先级的确定的
卡特兰
- 卡特兰数
前20项为(OEIS中的数列A000108):
1, 1, 2, 5, 14,
42, 132, 429, 1430, 4862,
16796, 58786, 208012, 742900, 2674440,
9694845, 35357670, 129644790, 477638700, 1767263190
公式:
假如有n个数依次进栈,出栈顺序可用卡特兰公式计算
例如:
f(0) = 1
f(4) = 14
f(4)=C(8,4)/5 = (8 * 7 * 6 * 5)/(4 * 3 * 2 * 1) / 5 = 14