代码之家 › 专栏 › 技术社区 › Cody

方案中缀到后缀

functional-programming scheme

Cody · 技术社区 · 16 年前

让我确定这是课堂作业的一部分,所以我绝对不会寻找完整的代码答案。本质上,我们需要用scheme编写一个转换器,它采用中缀格式表示数学方程的列表,然后用后缀格式输出一个包含该方程的列表。

我们已经得到了这样做的算法,非常简单。问题是,对使用任何可用的命令式语言功能都有限制。我不知道如何用一种纯粹的功能性方式来做这件事。这是我们在我的程序中首次介绍函数式编程。

我知道我将使用递归来迭代中缀表达式中的项列表。

(define (itp ifExpr)
  (
    ; do some processing using cond statement
    (itp (cdr ifExpr))
  ))

我已经实现了所有的处理(至少在不知道如何完成其余工作的情况下尽我所能做到最好),但是我用来实现这一点的算法要求将运算符推送到堆栈上,然后再使用。我的问题是如何在这个函数中实现所有递归调用都可用的堆栈?

2 回复 | 直到 16 年前

MichaÅ Marczyk 16 年前

(根据OP的评论进行了更新;请参阅原始答案下面的新部分。)

使用堆栈的列表并使其成为循环变量之一。例如。

(let loop ((stack (list))
           ... ; other loop variables here,
               ; like e.g. what remains of the infix expression
            )
  ... ; loop body
  )

然后,每当你想在下一次迭代中更改堆栈上的内容时,基本上就是这样做。

(loop (cons 'foo stack) ...)

还要注意,如果需要按顺序进行一系列“更新”,通常可以使用 let* 形式。这并不适用于scheme中的向量(尽管它确实适用于clojure的持久向量,如果您想查看它们的话),但它适用于标量值和列表以及srfi 40/41流。

针对您关于循环被排除为“命令式”功能的评论:

(let loop ((foo foo-val)
           (bar bar-val))
  (do-stuff))

是

(letrec ((loop (lambda (foo bar) (do-stuff))))
  (loop foo-val bar-val))

letrec 然后扩展为 let 可能会用到 set! 或局部 define 在内部,但被认为是完美的功能。你可以用其他符号代替 loop ,顺便说一句。而且,这种 让 被称为 让 '(或有时是'taged')。

你可能会记得 让 :

(let ((foo foo-val)
      (bar bar-val))
  (do-stuff))

也可以巧妙地使用 lambda :

((lambda (foo bar) (do-stuff)) foo-val bar-val)

所以这一切都可以归结为过程应用,这在scheme中是常见的。

命名 让 使自我递归更漂亮,仅此而已;我相信你已经知道, 在用函数的方式对迭代计算过程建模时,使用尾部调用的(自)递归是一种方法 .

显然,这个特殊的“loopy”结构也非常适合命令式编程——只需使用 集合! 或者循环体中的数据结构变异器,如果这是您想要做的——但是如果您远离破坏性函数调用,则循环递归或标记的 让 一点也不奇怪。 事实上,循环递归是函数式编程中最基本的技术之一,而这类作业的重点必须是准确地教授…-)

如果您真的不确定是否可以使用它(或者如果您只是使用 让 ,然后您可以按照上面的说明对其进行设计(可能使用本地 定义 而不是 莱特雷克 )

Zorf 16 年前

我不确定我是否完全正确地理解了这一点,但这个简单的解决方案有什么问题:

第一:

你要检验你的论点是否确实是一个列表:

如果是:将函数的映射追加到尾部(map postfixer(cdr lst))的a列表中,该列表只包含头部。映射只是将后缀程序再次应用于尾部的每个序列元素。

如果不是,只返回参数不变。

在我的实现中,有三行方案:

(postfixer '(= 7 (/ (+ 10 4) 2)))

到:

(7 ((10 4 +) 2 /) =)

通过映射的递归不需要循环,甚至不需要尾循环,也不需要变异,并且通过应用映射来显示函数风格。除非我完全误解了你的观点,否则我不认为有必要这么复杂。

编辑:哦,现在我读,中缀,不是前缀,到后缀。好吧,除了第二个元素,而不是第一个元素外,同样的想法也适用。