所以我正在用 C++ 编写一个基于 cmd 的计算器。我完成了它,但我想知道,在将中缀转换为后缀之后,我有一个名为后缀队列的队列,其中包含正确顺序的运算符/操作数。如何将后缀表达式转换回中缀?
1 回答
如果您不介意产生一些额外的括号,那应该很容易。你基本上像往常一样“评估”后缀数据,除了当你到达一个运算符时,而不是评估那个运算符并将结果压入堆栈,你打印出一个开放括号,第一个操作数,运算符,第二个操作数,最后是近括号。
如果您不介意更改顺序,那么避免多余的括号也很容易。向后走表达式,将事物从operator operand operand
into重新排列operand operator operand
。如果遇到需要操作数的运算符,则可以类似地打印出一个子表达式。当且仅当其运算符的优先级低于您之前遇到的运算符时,您才需要将该子表达式括在括号中。
例如,考虑:a b + c *
。向后走,我们得到*
, 然后c
,我们从打印出 开始c *
。然后我们需要另一个操作数,但是我们有一个+
,所以我们有一个子表达式。由于+
优先级低于*
,我们需要将该子表达式括在括号中,所以我们得到c * (b + a)
。
相反,如果我们有: a b * c +
,我们会以类似的方式开始生产,c +
但由于优先级高于,我们可以/可以打印出不带括号的(or )。*
+
a * b
b * a
请注意,使用-
or /
(或其他任何不可交换的东西)您必须更加小心地使操作数的顺序正确。即便如此,您也不会得到原始表达式,而只会得到一个在逻辑上应该与其等价的表达式。