使用最少括号括号后缀到中缀 [英] Postfix to Infix with minimum number of parentheses

问题描述

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

I am looking for algorithm postfix to infix notation which will produce the minimum number of the parentheses.

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

I have found that but it will produce many, many parentheses: http://tajendrasengar.blogspot.com/2011/09/postfix-to-infix-algorithm.html

例如

输入：

<ONP>abcd*/+~

结果：

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

推荐答案

如果您真的想要尽可能少的括号，您需要做什么，与您链接到的算法类似说。但是...

What you need to do if you really want as few parentheses as possible, is similar to what the algorithm you linked to says. However...

• 您应该为中的每个复合操作数存储运算符堆。即，操作数中使用的最后一个运算符。你可以使用第二个 Stack 。如果操作数不是复合操作，则可以将 null 添加到第二个堆栈，因为没有操作符。


• 不要用括号封装结果 String 。这在算法的其他地方完成（见下文）。

• You should store an operator for each composite operand in the Stack. Namely, the last operator used in the operand. You could use a second Stack for this. If the operand is not composite, you could add null to the second Stack, since there is no operator.
• Don't encapsulate the resulted String with parentheses. That is done elsewhere in the algorithm (see below).

当你从每个<$ c $中弹出前两个值时c>堆栈 s，您手头有3个运营商：

When you pop the top two values from each of the Stacks, you have 3 operators at hand:

• 当前运营商


• 第一个操作数中最后一个使用的运算符（如果运​​算符存在）


• 第二个操作数中最后一个使用的运算符（如果运​​算符存在）

根据这三个运算符，您应该在合并之前用括号封装第一个和/或第二个操作数。

Depending on these three operators, you should encapsulate the first and/or second operand with parentheses, before combining them.

您可以使用运算符优先级来确定是否应该有括号。订单如下：（无），{*，/}，{+， - }

You could use operator precedence to determine whether there should be parentheses. The order goes like this: (none), {"*", "/"}, {"+", "-"}

• 当且仅当其运算符的优先级低于当前运算符时，第一个操作数才需要括号。


• 第二个操作数需要括号如果其运算符的优先级低于当前运算符，或者它们具有相同的优先级，其中当前运算符是/或 - 。

• The first operand needs parentheses if and only if its operator has a lower precedence than the current operator.
• The second operand needs parentheses if its operator has a lower precedence than the current operator, or if they have equal precedence where the current operator is either "/" or "-".

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

The rest should be done the way your algorithm described.

这篇关于使用最少括号括号后缀到中缀的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！