中缀表达式与前缀后缀表达式的转换_中缀表达式转前缀表达式

表达式

• 在我们常见的运算操作中，它可表示为3部分组成：操作数、运算符、界限符。其中， 界限符就是我们在运算过程中所见到的()。它表示着计算的先后顺序，所以它是必不可少的。
  Eg：15➗(1+1)，在有界限符的情况下，它的运算顺序应该是：

1.先计算()中的操作，即先计算`1+1=2`
2.再计算15➗2=7.5
1
2

• 但是，如果我们将界限符也就是括号去掉，那么它的运算顺序应该为：

1.先计算15/1=15
2.再计算15+1=16
1
2

• 在去除界限符之后的两个操作中，结果截然不容。因此可见，界限符的重要性

中缀表达式

• 概述：中缀表示的是运算符的所在的位置，中缀表达式顾名思义，就是运算符在两个操作数中间，即操作数1 运算符 操作数2。在我们日常见到的所有表达式都是中缀表达式，它对于我们人类阅读和计算起来是非常遍历的，但是对于计算机而言，中缀表达式就显得不是那么遍历了。因此便出现了后缀表达式，也被称为逆波兰表达式(Reverse Polish notation)

后缀表达式

1. 与中缀表达式类似，它的后缀表达的也是运算符的所在位置，在后缀表达式中，运算符的位置应该是在两个操作数的后面，即操作数1 操作数2 运算符的格式。并且值得注意的是，在后缀表达式中，它转换后的运算符，就是它在原来的中缀表达式的运算顺序，所以在后缀表达式中并不需要界限符
2. 中缀表达式转为后缀表达式的手算方法：

1.确定中缀表达式中各个运算符的运算顺序
2.选择一个运算符，按照 [左操作数 右操作数 运算符] 的方式组合成一个新的表达式
3.如果还有运算符没有被处理，则转回步骤2
1
2
3

3. Eg：将 ( (15 ÷ ( 7 - ( 1 + 1 ) ) ) × 3 ) - ( 2 + ( 1 + 1 ) )转为对应的后缀表达式
   ①.先确定各个操作符的运算顺序
   
   ②.在确定各操作符的运算顺序后，选择最先计算的表达式即(1+1)进行转换，(1+1)转换为对应的后缀表达式后，它的格式应该为：1 1 +
   ③.还有运算符没有被处理，转回步骤2。选择下一个被处理的表达式(7-(1+1))，由于(1+1)已经被转换过了，所以直接将(1+1)替换为转换后的表达式，即7- (1 1 +)，此处的()只是为了方便我们将 1 1 +看作一个整体，并不存在。由于在表达式中，7是在1 1 +的左侧，所以在转换后7的位置也还是在表达式的左侧，并且值得注意的是，我们要将1 1 +看作是一个整体，我们将它看为变量x，那么原式就为7-x，它转换为后缀表达式应该为：7 x -，此时将1 1 +代回x，结果为：7 1 1 + -
   ④.还有运算符没有被处理，转回步骤2。选择下一个被处理的表达式((15 ÷ (7 - (1 + 1) ) )，由于在上面的操作中，我们已经将(7 - (1 + 1) ) )转为了对应的后缀表达式，所以在这里，我们同样将上一步转换好的表达式看为x，那么((15 ÷ (7 - (1 + 1) ) )就可以表示为：15 ÷ x，将它转换为对应的后缀表达式为：15 x ÷，将转换好的后缀表达式7 1 1 + -代回x，结果为：15 7 11 + - ÷
   ⑤.还有运算符没有被处理，转回步骤2。选择下一个被处理的表达式( (15 ÷ ( 7 - ( 1 + 1 ) ) ) × 3 )，与上面相似，由于在上一步已经将((15 ÷ (7 - (1 + 1) ) )的后缀表达式处理完毕，所以在这里用x代替该表达式，那么原表达式就可表示为：x * 3，将其转为后缀表达式，结果为：x 3 ×，将((15 ÷ (7 - (1 + 1) ) )的后缀表达式代回x，那么结果为：15 7 11 + - ÷ 3 ×。此处需要值得注意的点为在原表达式中是 x * 3，所以在转为后缀表达式之后，3的位置也应该是在右侧的操作数位置，注意不要颠倒顺序
   ⑥.还有未处理的操作符，转回步骤2。找到下一个要处理的表达式(1+1)。将它的结果与原有的后缀表达式拼接起来15 7 11 + - ÷ 3 × 1 1 +。在原表达式中,1+1原表达式的右侧，所以它所拼接的位置也是右侧
   ⑦.还有未处理的操作符，转回步骤2。找到下一个要处理的表达式2+(1+1)，此时我们用x代替上一步已经转换好的表达式，那么原表达式可表现为：2+x,将其转换为后缀表达式的形式，结果为：2 x +，将表达式代回x中，结果为：2 11 + +，将其与原有的表达式拼接起来，由于对于2+x这个操作，是在(1+1)这个操作的左侧，所以它拼接原有的后缀表达式的位置也应该在它的前面，所以结果为：15 7 11 + - ÷ 3 × 2 1 1 + +
   ⑧.还有未处理的操作符，转回步骤2。找到下一个要处理的表达式( (15 ÷ ( 7 - ( 1 + 1 ) ) ) × 3 ) - ( 2 + ( 1 + 1 ) )，此时由于-号左右两侧的后缀表达式都已经转换好了，所以直接将其放到原有的后缀表达式的最后方即可，结果为：15 7 11 + - ÷ 3 × 2 1 1 + + -
   ⑨.操作符全部处理完毕，终止本次操作。
4. 在后缀表达式的过程中，由于运算顺序不唯一，所以我们手算过程中对应的后缀表达式也不唯一。
   Eg：A + B * ( C - D ) - E / F，在表达式中，我们如果先算括号里的表达式，那么它所对应的运算顺序为：
   
   在该表达式中，它所对应的后缀表达式为：A B C D - * + E F / -。
   但是，在这个表达式中，如果我们先算最右侧的 E / F，结果也不会出错，所以我们可以得到一个与上面不一样的运算顺序，而它所对应的后缀表达式应该为：A B C D - * E F / - +。
   
   在这个表达式中，由于我们所规定的运算顺序不同，在同样的中缀表达式中得到了不同的后缀表达式，这显然是不符合算法的确定性的。因此，我们便需要通过一些约定来对它进行改变。我们约定只要左侧的运算符能先运行，那么我们就先运行左侧的运算符。
   同样是以 A + B * ( C - D ) - E / F为例，在遵循约定后，括号内的内容和最右侧的除法都可以先运行的情况下，我们先运行左侧的，那么处理的结果为：C D - 。此时B * (C - D)与最右侧的E / F都可以先运行，我们依然遵循左侧先运行的原则，那么结果为：B C D - * 。此时A + B*(C-D)与最右侧的E/F都可以运行，我们依然遵循左侧先运行的原则，那么结果为：A B C D - * +。此时我们只剩最右侧的- 与 / 两个操作符了，/的优先级高，因此我们先将E/F转为相应的后缀表达式：E F /，将其拼接到原有的后缀表达式中，得到的结果为：A B C D - * + E F /。最后将的运算应该是将-两边得到的表达式进行运算，那么最终得到的后缀表达式就为：A B C D - * + E F / -

前缀表达式

1. 与后缀表达式相反，在该表达式中，它的格式为：运算符 操作数1 操作数2
2. 中缀表达式转前缀表达式手算方法：

1.确定中缀表达式中各个运算符的运算顺序
2.选择下一个运算符，按照【运算符 左操作数 右操作数】的方式组合成一个新的表达式
3.如果还有运算符没被处理，转回步骤2
1
2
3

3. 注： 在转前缀表达式的过程中，也会遇到和转后缀表达式一样的情况，运算顺序不同可能会得到不同的前缀表达式，因此我们也需要进行一些约定确保在手算过程中，得到相同的前缀表达式结果。"右优先原则："只要右边的运算符能先计算，就优先计算右边的
4. Eg：将A + B * ( C - D ) - E / F转为对应的前缀表达式

1.最右侧的 E / F与中间括号的都可以先运行，但我们需要遵循右优先的规则，先运行右侧的表达式。
所以需要先将 E / F转为对应的前缀表达式：/ E F
2.此时应该计算的应该是括号中的内容，此时并没有可以和它同时运行的表达式，因此可直接转换。
得到的结果为：- C D
3.在转换完(C-D)的表达式后，下一步运算的应该是 B*(C-D)的结果，此时没有可以和它同时运行的表达式，可直接转化，得到的结果为：* B - C D
4.在计算完*、/、()这些表达式后，剩下的操作符只剩左侧的+与右侧的-，这两个表达式都可以先运行，我们遵循右优先原则，得到的结果为：- * B - C D
5.最后计算A +后面的表达式，得到的结果为：+ A - * B - C D
1
2
3
4
5
6
7