在使用C++或C#时,有没有将逆波兰表达式解释为“正常”数学表达式的方法?我在一家工程公司工作,他们偶尔会使用RPN,我们需要一种转换的方法。有什么建议吗?
我刚刚用Java写了一个版本,它在这里,还有一个用Objective-C编写的,在这里。
可能的算法:假设您有一个堆栈,其中输入为RPN格式,例如 8、9、*。您从第一个到最后一个遍历数组,并始终删除当前元素。对此元素进行评估。如果它是操作数,则将其添加到结果堆栈中。当它是运算符时,您弹出结果堆栈两次(对于二进制运算)以获得操作数,并在结果堆栈上写入结果字符串。
对于输入 "8, 9, +, 2, *",您会在结果堆栈上获得这些值(方括号表示单个元素):
步骤1:[8]
步骤2:[8],[9]
步骤3:[(8 + 9)]
步骤4:[(8 + 9)], [2]
步骤5:[(8 + 9) * 2]
当输入栈为空时,您已完成,resultStack的唯一元素就是您的结果。(请注意,输入可能包含多个条目或不合理的条目,例如前导操作:“+ 2 3 /”)。
链接中的实现故意不使用任何自制类型,例如运算符或操作数,也不应用复合模式等。它很简洁明了,因此可以轻松理解并移植到任何其他语言。
将其移植到C#很简单。
如果您有一些源文本(字符串)需要从RPN(后缀表示法)转换为“正常表示法”(中缀表示法),这是完全可能的(而且可能不太困难)。
RPN是为基于堆栈的机器设计的,因为操作的表示方式(“2 + 3” -> “2 3 +”)符合它在硬件上实际执行的方式(将“2”推入堆栈,将“3”推入堆栈,弹出堆栈上的前两个参数并将它们相加,再将结果推回堆栈)。
基本上,您想通过将要操作的2个表达式作为“叶节点”,其后跟的操作本身作为“父节点”,从您的RPN创建一个语法树。这可能是通过递归地查看输入字符串来完成的(如果尚未正确括号化子表达式,则可能需要确保它们正确括号化以获得额外的清晰度)。
一旦您拥有了该语法树,您可以通过对该树进行先序遍历、后序遍历或中序遍历来输出前缀、后缀或中缀表示法(如果需要,可以括号化输出以获得清晰度)。
更多信息可以在此处找到。