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

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