数据结构小知识整理

中缀式转换为前缀式以及后缀式

• 假设中缀表达式为：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