后缀到后缀的括号最少

Question

我正在寻找后缀符号表示法的算法，该算法将产生最小数量的括号。

我发现它会产生很多括号：http : //tajendrasengar.blogspot.com/2011/09/postfix-to-
infix-algorithm.html

例如

输入：

<ONP>abcd*/+~

结果：

<INF>~(a+b/(c*d))

Answer 1

如果您确实希望尽可能地减少括号，则需要执行的操作与链接的算法类似。然而…

• 您应该为中的每个 复合 操作数存储一个运算符Stack。即，操作数中使用的最后一个运算符。您可以Stack为此花一秒钟。如果操作数不是复合数，则可以添加null到第二个Stack，因为没有运算符。
• 不要将结果String用括号括起来。这是在算法的其他地方完成的（请参见下文）。

从每个Stacks 弹出顶部的两个值时，手边有3个运算符：

• 当前的运营商
• 第一个操作数中最后使用的运算符（如果该运算符存在）
• 第二个操作数中最后使用的运算符（如果该运算符存在）

取决于这三个运算符，在组合它们之前，应该用括号封装第一个和/或第二个操作数。

您可以使用运算符优先级来确定是否应包含括号。顺序如下：(none), {"*", "/"}, {"+", "-"}

• 当且仅当第一个操作数的运算符的优先级低于当前运算符的优先级时，才需要括号。
• 第二个操作数需要括号如果操作者具有比当前操作者一个低优先级，或如果它们具有相同的优先级，其中电流运算符为"/"或"-"。

其余应按照算法描述的方式进行。