前中后缀表达式

发表于 | 分类于

中缀表达式对应中序遍历，前缀对应前序遍历，后缀对应后序遍历。之所以可以转换，我想是因为：

  1. 标准的满二叉树，非多叉。
  2. 运算符优先级一定。
  3. 操作数均为叶子，操作符均为内部节点。

中缀转后缀

定义优先级：(, ) > *, / > +, - > 空栈。 定义输出操作为：push back

  1. 构造一个空的运算符栈
  2. 对中缀表达式从左至右扫描，遇到操作数直接输出，遇到其它符号a处理如下
  3. 比较和栈顶符号b优先级大小，若a>b，则将a压入栈：此时说明当前运算符左侧表达式扫描完毕，但只存在不可输出的低优先级表达式
  4. 若a<=b，则将栈顶依次弹出，直到新的栈顶元素b’满足a>b’，再将a入栈：此时说明左侧表达式扫描完毕，且存在可以输出的相同或更高优先级表达式
    • 对于)，直到遇到(，两个元素均弹出
  5. 若扫描完毕，栈中仍有字符，依次输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 假设此时扫描到*，说明*左侧表达式扫描完，
// 但当前表达式缓存部分优先级低，自己构成它的一部分，不可输出
   +
 /   \
100   *
    /   \
   20   19
// 假设此时扫描到+，说明+左侧表达式扫描完，
// 且当前表达式缓存部分优先级相同或更高，构成自己的左侧部分，可以输出
       *
     /   \
    *    20
  /   \
  5   3

中缀转前缀

定义优先级：(, ) > *, / > +, - > 空栈。 定义输出操作为：append_front

  1. 构造一个空的运算符栈
  2. 对中缀表达式从右至左扫描，遇到操作数直接压入结果栈，遇到其它符号a处理如下
  3. 比较和栈顶符号b优先级大小，若a>=b，则将a压入栈：此时说明
  4. 若a<b，则将栈顶依次弹出，直到新的栈顶元素b’满足a>=b’，再将a入栈：
    • 对于(，直到遇到)，两个元素均弹出
  5. 若扫描完毕，栈中仍有字符，依次输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 假设此时扫描到第二个*，说明*右侧表达式扫描完，
// 但当前表达式缓存部分优先级相同或较低，自己构成它的左部分，不可以输出
       *
     /   \
    *    20
  /   \
  5   3
// 假设此时扫描到+，说明+右侧表达式扫描完，
// 且当前表达式缓存部分优先级高，它构成自己的右部分，可以输出
   +
 /   \
100   *
    /   \
   20   19

后缀转中缀

构造表达式树。

  1. 构造一个节点栈
  2. 从左向右扫描后缀表达式，如果遇到数字，构造叶子节点入栈。
  3. 如果遇到运算符，则弹出两个节点。后弹出的节点作为第一操作数，用运算符作为子树的根节点生成子树。再将根节点入栈。

前缀转中缀

构造表达式树。

  1. 构造一个节点栈
  2. 从右向左扫描前缀表达式，如果遇到数字，构造叶子节点入栈
  3. 如果遇到运算符，则弹出两个节点。先弹出的节点作为第一操作数，用运算符作为子树的根节点生成子树，再将根节点入栈。

参考

  • https://blog.csdn.net/walkerkalr/article/details/22798365