Chr*_*ung 15
是.想想RPN计算器的工作原理.现在,不是计算值,而是将操作添加到树中.因此,例如,2 3 4 + *当你到达+时,然后放入堆栈,而不是将7放在堆栈(+ 3 4)上.同样,当你到达*(你的堆栈看起来就像2 (+ 3 4) *在那个阶段),它就变成了(* 2 (+ 3 4)).
这是前缀表示法,然后您必须将其转换为中缀.从左到右遍历树,深度优先.对于每个"内部级别",如果运算符的优先级较低,则必须将操作放在括号中.在这里,你会说,2 * (3 + 4)因为+的优先级低于*.
希望这可以帮助!
编辑:有一个微妙的(除了不考虑上面的一元操作):我假设左关联运算符.对于右关联(例如**),那么对于2 3 4 ** **⇒ (** 2 (** 3 4))与2 3 ** 4 **⇒ ,您会得到不同的结果(** (** 2 3) 4).
当从树中重构中缀时,两种情况都表明优先级不需要包围,但实际上后一种情况需要括号((2 ** 3) ** 4).因此,对于右关联运算符,左侧分支需要具有更高优先级(而不是更高或相等)以避免包围.
此外,进一步的想法是你需要括号-和/操作符的右侧分支.