signed

QiShunwang

“诚信为本、客户至上”

每日一题———23.中缀表达式转换

2021/6/9 0:20:14   来源:

前言

数据结构每日一题

声明:因个人能力有限,本文仅是个人的学习记录笔记,有错误之处还望指出


中缀转后缀的方法

常规方法

  1. 遇到操作数(a,b,c)的时候:直接输出,添加到后缀表达式中
  2. 栈为空的时候,遇到运算符直接输出
  3. 遇到左括号:将其入栈
  4. 遇到右括号:执行出栈操作,并将出栈的元素输出,直到弹出的元素是左括号(左括号不输出直接删除)
  5. 遇到其他运算符:加减乘除,弹出所有优先级大于或等于该运算符的栈顶元素,然后将该运算符入栈
    比较入栈元素和栈顶元素,只有优先级小于栈顶元素才入栈,其余都出栈
  6. 最终将栈的元素依次出栈输出

二叉树的方法

  1. 将中缀表达式转化成二叉树的形式
  2. 后缀表达式就是该二叉树的后序遍历
  3. 前缀表达式就是该二叉树的先序遍历

如下所示
在这里插入图片描述

易错知识点

  1. 循环队列是尾插头删
  2. 哈希查找的平均查找长度与装填因子有关,查找效率不依赖表中的项数和表长
  3. 装填因子=表中的项数n/表长m
而塞过 2021-6-8