方案中缀到后缀

发布于 2024-08-28 07:49:35 字数 465 浏览 4 评论 0原文

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

我们已经获得了执行此操作的算法，非常简单。问题是使用任何可用的命令式语言功能都受到限制。我不知道如何以纯粹的功能方式做到这一点。这是我们在我的程序中对函数式编程的第一次介绍。

我知道我将使用递归来迭代中缀表达式中的项目列表，如下所示。

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

我已经实现了所有处理（至少在不知道如何执行其余操作的情况下尽我所能），但是我用来实现此操作的算法要求将运算符推入堆栈并稍后使用。我的问题是如何在此函数中实现一个可供所有递归调用使用的堆栈？

原文

Let me establish that this is part of a class assignment, so I'm definitely not looking for a complete code answer. Essentially we need to write a converter in Scheme that takes a list representing a mathematical equation in infix format and then output a list with the equation in postfix format.

We've been provided with the algorithm to do so, simple enough. The issue is that there is a restriction against using any of the available imperative language features. I can't figure out how to do this in a purely functional manner. This is our fist introduction to functional programming in my program.

I know I'm going to be using recursion to iterate over the list of items in the infix expression like such.

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

I have all of the processing implemented (at least as best I can without knowing how to do the rest) but the algorithm I'm using to implement this requires that operators be pushed onto a stack and used later. My question is how do I implement a stack in this function that is available to all of the recursive calls as well?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

帥小哥 2024-09-04 07:49:35

（根据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 的语法糖

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

，然后扩展为 let 的形式，它可能使用等效的东西内部的 set! 或本地 define，但被认为功能完美。顺便说一句，您可以自由地使用其他符号来代替循环。另外，这种 let 称为“命名 let”（有时称为“标记”）。

您可能会记得，let: 的基本形式

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

也是巧妙使用 lambda: 的语法糖，

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

因此这一切都归结为过程应用程序，就像在Scheme 中常见的那样。

命名为 let 使自递归更漂亮，仅此而已；我相信您已经知道，带有尾部调用的（自）递归是以函数方式对迭代计算过程进行建模时的最佳选择。

显然，这种特殊的“循环”构造也非常适合命令式编程——如果您想做的话，只需在循环体中使用 set! 或数据结构变异器——但如果您远离从破坏性函数调用来看，循环递归或标记的 let 本身根本没有什么本质上的必要。 事实上，循环递归是函数式编程中最基本的技术之一，这种作业的全部要点必须准确地教授...:-)

如果你真的感到不确定关于是否可以使用它（或者如果您只使用命名的let，它是否足够清晰，您可以理解所涉及的模式），那么您可以按照上面的解释对其进行脱糖（可能使用本地 define 而不是 letrec）。

(Updated in response to the OP's comment; see the new section below the original answer.)

Use a list for the stack and make it one of the loop variables. E.g.

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

Then whenever you want to change what's on the stack at the next iteration, well, basically just do so.

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

Also note that if you need to make a bunch of "updates" in sequence, you can often model that with a let* form. This doesn't really work with vectors in Scheme (though it does work with Clojure's persistent vectors, if you care to look into them), but it does with scalar values and lists, as well as SRFI 40/41 streams.

In response to your comment about loops being ruled out as an "imperative" feature:

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

is syntactic sugar for

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

letrec then expands to a form of let which is likely to use something equivalent to a set! or local define internally, but is considered perfectly functional. You are free to use some other symbol in place of loop, by the way. Also, this kind of let is called 'named let' (or sometimes 'tagged').

You will likely remember that the basic form of let:

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

is also syntactic sugar over a clever use of lambda:

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

so it all boils down to procedure application, as is usual in Scheme.

Named let makes self-recursion prettier, that's all; and as I'm sure you already know, (self-) recursion with tail calls is the way to go when modelling iterative computational processes in a functional way.

Clearly this particular "loopy" construct lends itself pretty well to imperative programming too -- just use set! or data structure mutators in the loop's body if that's what you want to do -- but if you stay away from destructive function calls, there's nothing inherently imperative about looping through recursion or the tagged let itself at all. In fact, looping through recursion is one of the most basic techniques in functional programming and the whole point of this kind of homework would have to be teaching precisely that... :-)

If you really feel uncertain about whether it's ok to use it (or whether it will be clear enough that you understand the pattern involved if you just use a named let), then you could just desugar it as explained above (possibly using a local define rather than letrec).

回复收藏 0 原文

心凉 2024-09-04 07:49:35

我不确定我是否正确理解了这一切，但是这个更简单的解决方案有什么问题：

首先：

您测试您的参数是否确实是一个列表：

如果是：在尾部附加函数的 MAP (map postfixer (cdr lst )) 到仅包含头部的列表。 Map 只是再次将后缀器应用于尾部的每个顺序元素。

如果不是，则直接返回参数不变。

我的实现中的三行Scheme翻译为：

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

到：

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

通过map的递归不需要循环，甚至不需要尾循环，不需要突变，并通过应用map显示功能风格。除非我完全误解了你的观点，否则我认为不需要上述所有复杂性。

编辑：哦，现在我读到，中缀，而不是前缀，到后缀。好吧，除了采用第二个元素而不是第一个元素之外，同样的一般思想也适用。

I'm not sure I understand this all correctly, but what's wrong with this simpler solution:

First:

You test if your argument is indeed a list:

If yes: Append the the MAP of the function over the tail (map postfixer (cdr lst)) to the a list containing only the head. The Map just applies the postfixer again to each sequential element of the tail.

If not, just return the argument unchanged.

Three lines of Scheme in my implementation, translates:

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

To:

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

The recursion via map needs no looping, not even tail looping, no mutation and shows the functional style by applying map. Unless I'm totally misunderstanding your point here, I don't see the need for all that complexity above.

Edit: Oh, now I read, infix, not prefix, to postfix. Well, the same general idea applies except taking the second element and not the first.

回复收藏 0 原文

~没有更多了~