2

我正在尝试制作从后缀到中缀符号的转换器，需要一些帮助。已经有一个关于中缀到后缀转换的问题，它给出了一个我无法转换回来的例子。（注意：那里缺少减号！）

以下是我的转换器的输出，其中第一个“列”是后缀输入，第二个是我的中缀输出，第三个是我可能应该得到的（？）：

2 -                      =   - 2                           =?    - 2                       true
1 + 2 +                  =   + 1 + 2                       =?    + 1 + 2                   true
1 + 2 + +                =   + (+ 1 + 2)                   =?    + 1 + + 2                 false
1 + 2 + + 3 - - 4 - -    =   - (- (+ (+ 1 + 2) - 3) - 4)   =?    + 1 + + 2 - - 3 - - 4     false

你认为有可能解决这个问题，还是最后两行实际上转换正确？你会如何编写算法来解决这个问题？

请假设更多的运算符（不仅是+and -）可以设置为一元和二元，其中一元运算符的优先级高于二元运算符。

参考

  1. Ruby Quiz #148: Postfix to Infix，同样来自Google Groups
  2. 在 LiteratePrograms 上具有一元运算符支持的调车场算法（C、Python、Perl）
4

1 回答 1

1

后缀表示法没有优先级的概念，因为任何运算符的操作数始终是堆栈上的顶部 N 值（然后由运算符的结果替换。

后缀表示法的一个问题是它不能很好地处理运算符符号，这些运算符符号可以根据操作数的数量引用不同的运算符（例如 -，它可以表示一元或二元减号）。唯一的出路是确保每个运营商都有一个唯一的符号来代表它。

于 2010-08-25T14:58:43.613 回答