我需要一种使用递归评估后缀表达式的算法。在此后缀表达式中,操作数可以是多于一位的数字。空格用于区分两个操作数。因此表达式“45 68 +”是有效的。
我想过以相反的方向评估它,但我认为这不应该是正确的。
有人可以帮我解决算法吗?
提前致谢。
最佳答案
我觉得这不是一个递归友好的问题。但我确信可以这样做。
我想到了两种方法:
选项#1:使函数递归调用和返回与 Wiki 上描述的堆栈压入和弹出操作相匹配。
这种方法的缺点是您很快就会发现函数返回的数据可能相当复杂。可能是一个运算符(operator)。也许带有可选操作数(即:数字)。您将返回可能应该对其进行操作(方法)的结构/对象。
选项#2:每个递归调用都会处理输入流的下一个字符。
我认为这种方法会作为参数传入堆栈,并且可能会传入当前数字的“累加器”——在将数字插入堆栈之前将数字累加到一个数字中。将返回一个大量的尾递归数字结果。
这种方法实际上只是将循环重写为递归。
无论哪种方式,自己弄清楚应该具有挑战性和教育意义!
关于java - 使用递归计算后缀表达式,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8074416/