algorithm - 以最少的步骤转换为正确的后缀表示法

Question

由操作数和二元运算符组成的表达式可以用逆波兰表示法 (RPN) 编写，方法是在操作数后跟运算符。例如，3 + (4 * 5) 可以写成“3 4 5 * +”。

给你一个由 x 和 * 组成的字符串。 x 表示操作数，* 表示二元运算符。很容易看出并非所有此类字符串都代表有效的 RPN 表达式。例如，“x*x”不是有效的 RPN 表达式，而“xx*”和“xxx**”是有效的表达式。将给定字符串转换为有效的 RPN 表达式所需的最少插入、删除和替换操作数是多少？

输入:第一行包含测试用例T的数量。后面是T个测试用例。每个 case 包含一个仅由字符 x 和 * 组成的字符串。

输出:输出 T 行，每个测试用例包含所需的最少操作数。

约束:1 <= T <= 100 输入字符串的长度最多为 100。

示例输入:

5
x
xx*
xxx**
*xx
xx*xx**

示例输出:

0
0
0
2
0

解释:

对于前三种情况，输入的表达式已经是一个有效的RPN，所以答案为0。对于第四种情况，我们可以进行一次删除，一次插入操作:xx -> xx -> xx

Answer 1

这是一个不同寻常的大答案。如果还有一个优雅的双线，我不会感到惊讶，但在我发布之前，这是我的。

假设您有一个简单的 2D 图，其中 x 轴表示解析步骤，y 轴表示当前 X 数与星数 n(x)-n(*) 之间的差值。例如，对于输入 xx*xx**，图形将是这样的:

╫
╫         +
╫   +   +   +
╫ +   +       +
╬═╧═╧═╧═╧═╧═╧═╧
  x x * x x * *

为了使表达式有效，此图在 y 轴上绝不能达到零或以下，并且最后 y 的值必须为 1(堆栈中留下单个值)。

给定了三种用于输入表达式的操作:插入、删除和替换。这个替换操作实际上是两者之一:用*替换x，用x替换*。当您在表达式中间的某处应用插入或删除时，图形会发生变化，以便从该点开始，图形中的所有点都向上或向下移动。应用替换时，点会在图中向上或向下移动两个缺口。一个有趣的注意事项:我们不必处理删除操作，因为结果与应用相反的插入是相同的，不同之处在于插入可以始终应用，而只有在有可用符号时才删除。

您的目标是找到最少数量的操作。如果我们只观察最终目标 (y=1)，那么我们将确定我们必须移动图形的缺口数，并应用尽可能多的替换操作和一个额外的插入操作。如果 N(x)-N(*) 的总和为 N，则操作数将为 floor((N-1)/2)。该标志确定要应用哪些操作。

问题是我们必须注意另一个条件，即图形绝不能达到零。为了确定这一点，我们必须首先对我们的表达式应用之前的操作。 'Insert x'在开头添加，'insert *'在末尾，从头开始搜索并替换每个*为x，并从末尾向后搜索并替换每个x为*。

在这一步之后我们有了新的表达。从头开始迭代，寻找 y=0 的地方。如果有这样的地方，那么你必须在它之前插入一个x，并在表达式末尾插入一个*来补偿。但请记住，您可能已经这样做了(在开始处插入 x，或在结尾处插入 *)。如果你有两个插入 x 然后假装它实际上是用 x 替换 * (少一个操作)，而忘记必须插入 x。与一对插入物 * 类似:删除两个插入物 *，并再应用一个“用 * 替换 x”。您确实必须应用它，即更改表达式，因为如果从末尾搜索时发现的 x 实际上在您当前位置之前，那么您将无法应用替换，因此无法将两个插入操作压缩为一个替换。

继续迭代直到结束，计算额外的操作，并且始终记住是否有一个插入 x 和一个插入 *。应该是这样。最后你会有一些操作。