C++ 将后缀转换为中缀

Question

所以我正在用 C++ 编写一个基于 cmd 的计算器。我完成了它，但我想知道，在将中缀转换为后缀之后，我有一个名为后缀队列的队列，其中包含按正确顺序排列的运算符/操作数。如何将后缀表达式转换回中缀？

Answer 1

如果您不介意产生一些额外的括号，那应该很容易。你基本上像往常一样“评估”后缀数据，除了当你到达一个运算符时，而不是评估该运算符并将结果压入堆栈，你打印出一个开括号，第一个操作数，运算符，第二个操作数，最后是闭括号。

如果您不介意更改顺序，也很容易避免多余的括号。向后走表达式，将 operator operand operand 中的内容重新排列为 operand operator operand。如果遇到需要操作数的运算符，则有一个子表达式可以类似地打印出来。当且仅当其运算符的优先级低于您之前遇到的运算符时，您才需要将该子表达式括在括号中。

例如，考虑:a b + c *。向后走，我们得到 *，然后是 c，所以我们首先打印出 c *。然后我们需要另一个操作数，但是我们有一个+，所以我们有一个子表达式。由于 + 的优先级低于 *，我们需要将该子表达式括在括号中，因此我们得到 c * (b + a) .

相反，如果我们有:a b * c +，我们会以类似的方式开始，生成 c +，但是因为 * 是比 + 更高的优先级，我们可以打印出 a * b(或 b * a) parent 。

请注意，对于 - 或 /(或任何其他不可交换的)，您必须更加小心地确保操作数的顺序正确.即便如此，您也不会取回原始表达式，只能取回逻辑上应与其等价的表达式。