# 三种表达式

• 前缀表达式 / Prefix Notation

  • 波兰式 / Polish Notation

• 中缀表达式 / Infix Notation (中缀表达式才需要有括号)

• 后缀表达式 / Postfix Notation

  • 逆波兰式 / Reverse Polish Notation

# 三种表达式的相互转化

# 括号法

通用方法，略

# 表达式树法

通用方法，略

# 栈方法

专用于： 中缀 -> 前缀 / 后缀

很像，注意区别，对照记忆

# 中缀 -> 后缀

• 从左到右扫描
• 从右到左打印
• 遇到操作数：直接打印
• 遇到操作符：
  1. 优先级小于等于栈顶：栈顶出栈并打印，继续与下一个栈顶操作符比较
  2. 优先级大于栈顶：入栈
  3. 栈顶为括号 (一定是左括号)：入栈
• 遇到括号：
  1. 左括号：直接入栈
  2. 右括号：不断出栈并打印，直到出栈一个左括号为止

# 中缀 -> 前缀

• 从右到左扫描
• 从左到右打印
• 遇到操作数：直接打印
• 遇到操作符：
  1. 优先级小于栈顶：栈顶出栈并打印，继续与下一个栈顶操作符比较
  2. 优先级大于等于栈顶：入栈
  3. 栈顶为括号 (一定是右括号)：入栈
• 遇到括号：
  1. 左括号：不断出栈并打印，直到出栈一个右括号为止
  2. 右括号：直接入栈