中缀、前缀、后缀表达式

文章目录中缀、前缀、后缀表达式一、基本概念二、中缀表达式三、后缀表达式逆波兰式四、前缀表达式波兰式五、中缀转后缀借助栈六、中缀转前缀借助栈七、三者对比总结八、关键注意点中缀、前缀、后缀表达式一、基本概念类型运算符位置日常使用示例中缀表达式运算符在两个操作数中间人类常用a b前缀表达式波兰式运算符在两个操作数前面少见 a b后缀表达式逆波兰式运算符在两个操作数后面计算机常用a b 二、中缀表达式定义运算符写在两个操作数之间就是我们日常书写的数学表达式。特点需要括号来改变运算优先级需要记住运算符优先级括号 乘除 加减对人类友好但对计算机不友好解析复杂示例(a b) * c - d三、后缀表达式逆波兰式定义运算符紧跟在其对应的操作数之后无需括号运算顺序完全由运算符的位置决定。核心本质从左往右扫描操作数先到等运算符来了再计算。求值规则从左往右扫描表达式遇到操作数→ 压入栈中遇到运算符→ 弹出栈顶两个操作数先弹出的是右操作数后弹出的是左操作数计算后将结果压回栈中表达式结束时 → 栈中唯一的值就是最终结果示例中缀(a b) * c→ 后缀a b c *验证a1, b2, c3读a(1) → 入栈栈 [1]读b(2) → 入栈栈 [1, 2]读→ 弹出 2右和 1左算 123入栈栈 [3]读c(3) → 入栈栈 [3, 3]读*→ 弹出 3右和 3左算 3×39入栈栈 [9]结果 9与 (12)×3 9 一致减法验证中缀a - b→ 后缀a b -a5, b3读a(5) → 入栈栈 [5]读b(3) → 入栈栈 [5, 3]读-→ 弹出 3右和 5左算 5-32入栈栈 [2]结果 2与 5-3 2 一致四、前缀表达式波兰式定义运算符写在操作数之前。核心本质从左往右扫描运算符先到等操作数到齐再计算。求值规则从左往右扫描表达式遇到运算符→ 先记着等待操作数遇到操作数→ 压入栈中当某个运算符的两个操作数都到齐时 → 弹出操作数先弹出的是左操作数后弹出的是右操作数计算后将结果压回栈中表达式结束时 → 栈中唯一的值就是最终结果示例中缀(a b) * c→ 前缀* a b c验证a1, b2, c3读*→ 运算符先记着读→ 运算符先记着读a(1) → 入栈栈 [1]读b(2) → 入栈栈 [1, 2]的操作数齐了 → 弹出 1左和 2右算 123入栈栈 [3]读c(3) → 入栈栈 [3, 3]*的操作数齐了 → 弹出 3左和 3右算 3×39入栈栈 [9]结果 9与 (12)×3 9 一致减法验证中缀(a - b) * c→ 前缀* - a b ca5, b3, c2读*→ 记着读-→ 记着读a(5) → 入栈栈 [5]读b(3) → 入栈栈 [5, 3]-的操作数齐了 → 弹出 5左和 3右算 5-32入栈栈 [2]读c(2) → 入栈栈 [2, 2]*的操作数齐了 → 弹出 2左和 2右算 2×24入栈栈 [4]结果 4与 (5-3)×2 4 一致五、中缀转后缀借助栈算法步骤从左到右扫描中缀表达式遇到操作数→ 直接输出遇到左括号(→ 压入栈遇到右括号)→ 不断弹出栈顶运算符并输出直到弹出左括号遇到运算符→ 与栈顶运算符比较优先级若栈顶优先级 ≥ 当前运算符 → 弹出栈顶并输出继续比较否则 → 将当前运算符压入栈扫描结束后 → 将栈中剩余运算符依次弹出输出示例(a b) * c→a b c *六、中缀转前缀借助栈算法步骤先将中缀表达式逆序同时左右括号互换按中缀转后缀的方法处理注意优先级比较方向相反将最终结果再次逆序即为前缀表达式示例(a b) * c→* a b c七、三者对比总结对比项中缀前缀后缀运算符位置中间前面后面是否需要括号需要不需要不需要扫描方向求值—从左往右从左往右计算机友好度低高高人类友好度高低低一句话记忆中缀给人看前缀和后缀给机器算。前缀和后缀的求值逻辑是互补的前缀先遇到运算符等操作数到齐再计算后缀先遇到操作数等运算符来了再计算八、关键注意点前缀和后缀的求值方向都是从左往右不存在从右往左扫描前缀和后缀的弹出顺序相反后缀先弹出的是右操作数后弹出的是左操作数前缀先弹出的是左操作数后弹出的是右操作数这一点在减法和除法中尤为关键顺序搞反结果就错了笔记改好了要不要我出几道中缀转前缀、前缀转中缀的练习题帮你把这块知识串起来