将内缀转换为后缀

Question

我应该将以下内容转换为后缀形式：（A B*C）/（D-E*F）

我得到了这个答案：ABC*DEF*-/

这是正确的吗？如果我使用了错误的后缀形式，那么之后还有很多问题都是不正确的。如果我错了，你能告诉我为什么吗？谢谢你的帮助。

Answer 1

是的，通过迭代返回是一种方法来检查这一点，但您也可以将此表达式从从内缀开始转换为postfix。表达式：-（BC）/（D-EF）从表达式中的第一个符号开始。

symbol                stack(operator)              postfix(operand)
 (                        (
  A                       (                           A 
  +                       (+                          A
  B                       (+                          AB
  *                       (+*                         AB
  C                       (+*                         ABC
  )                       (+*)                        ABC
     as bracket closes every symbol inside bracket popout(LIFO)
                                                      ABC*+
  /                       /                           ABC*+
  (                       /(                          ABC*+
  D                       /(                          ABC*+D
  -                       /(-                         ABC*+D
  E                       /(-                         ABC*+DE
  *                       /(-*                        ABC*+DE
  F                       /(-*                        ABC*+DEF
  )                       /(-*)                       ABC*+DEF
                            /                         ABC*+DEF*-
   as all symbol have been done operator left in stack will popout(LIFO)
                                                      ABC*+DEF*-/

随着高优先级运算符的出现，它可以被放在已经具有低优先级运算符的堆栈中，但在相反的情况下，如果堆栈中的高优先级运算符和低优先级符号出现，则高优先级运算符将从堆栈中弹出到后缀表达式。注意：-没有两个相同优先级的操作符可以在堆栈中保持在一起，因为第二个操作符出现，相同优先级的第一个操作符将弹出。

Answer 2

我知道这是个陈词滥调，但这是事实

这是正确的形式。您可以通过自己迭代后缀并将其转换回中缀来轻松检查它，就像这样，从空堆栈开始。

A是数组中的第一个元素，它是一个数字，因此将它推到堆栈上。这同样适用于B和C。因此，堆栈现在是A、B、C`。

下一个令牌是一个运算符（*），它需要两个操作数。因此，从堆栈中弹出前两个操作数，或B和C。将两者合并，由操作员分隔，并将其推到堆栈上。为了简化算法，只需在所有内容周围加上括号。您的堆栈现在是A，（B*C）。

下一个令牌是另一个二进制运算符（）。重复与上面相同的过程，得到的堆栈为（A（B*C））。

对其余部分重复此过程，您将得到一个等价于（ab*C）/（D-E*F）