使用最少数量的括号将后缀修复为Infix

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), {"*", "/"}, {"+", "-"}

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

其余的应该按照算法描述的方式完成.