前缀、中缀、后缀表达式

三种表达式

• 前缀表达式 / Prefix Notation

• 波兰式 / Polish Notation

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

• 后缀表达式 / Postfix Notation

• 逆波兰式 / Reverse Polish Notation

三种表达式的相互转化

括号法

通用方法，略

表达式树法

通用方法，略

栈方法

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

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

中缀 -> 后缀

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

中缀 -> 前缀

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