如何在 Scheme 中仅使用 1 个列表来构建 2 个列表？

Question

我正在尝试做一个将字符列表作为输入的函数，returns一个包含条件中给定特定字符之前的所有字符的列表，以便我可以计算后缀表达式.

示例：用户输入字符串" 5 =b 10 * =c "

我做的第一步是使用 string->list 将此字符串转换为列表，所以我得到这样的列表

(# #\space #\=#\b #\space # #\space #\* #\space #\=#\c #\space)

然后我开始阅读列表，一旦我阅读了字符 #\= 就停止了，我将它之前的所有字符放在 list1 中，然后是字符之后的所有内容 list2。所以我得到 list1 (#) 并且 list2 是 (#\b #\space # #\space #\* #\space #\=#\c #\space)

然后我将 5 分配给 b 即 (car list2)，然后继续阅读 list2 直到我阅读另一个 =，然后我将第二个 = 之前的所有元素放在列表中 (#\b #\space # #\space #\*) 的列表中，然后我计算 b * 10 ，并将结果存储在 c 这是第一个元素最后一个列表。

这个函数是我写的

(define affect
  (lambda(l1 l2 l3)
    (cond ((null? l1)'())
          ((eq? (car l1) #\=)(append(cons (cdr l1)l2)))
          (else (affect (cdr l1)(cons(car l1)l2)l3)))))

但似乎这并不是我真正想要的，而且一切都变得越来越复杂...有什么想法吗？只是提出一个想法如何解决这样的问题。

Answer 1

你没有提到你使用的是哪种实现，所以我将使用我最熟悉的 Racket。

一些备注：

我不明白你为什么要在这里管理变量，因为它们还没有被使用
这是一个 RPN 计算器，因此您需要有某种堆栈（列表在这里非常方便）
我宁愿在这里使用字符串而不是字符

我使用 命名的 let 创建了一个工作实现，这是我将在此处使用的循环结构。我也在使用 let* 和 Racket 的一些方便的程序，如 substring 和 string-split。我不知道你是否被允许使用这些，但你总是可以自己创建它们。

所以这是一个示例实现，它既不完整也不万无一失，但它正确地处理了您的示例输入：

(define (evaluate str)
  (let loop ((lst (string-split str)) ; named let for looping
             (stack '())
             (vars '()))
    (printf "lst=~v  stack=~a  vars=~a\n" lst stack vars) ; display, for debugging purposes
    (if (null? lst)
        (car stack)  ; done, return top of stack
        (let* ((c  (car lst))           ; element to process
               (n  (string->number c))  ; try to convert c to a number; returns #f if ko
               (op (string->symbol c))) ; convert c to a symbol
          ; recursive call to loop
          (loop
           ; first element is replaced by rest of list
           (cdr lst)
           ; second element is the (updated) stack
           (cond
             (n           (cons n stack))
             ((eq? op '*) (cons (* (first stack) (second stack)) (cddr stack)))
             (else        stack))
           ; third element is the (updated) list of variables
           (if (string=? (substring c 0 1) "=")
               (cons (list (substring c 1) (car stack)) vars)
               vars))))))

display 将显示中间结果：

> (evaluate "5 =b 10 * =c ")
lst='("5" "=b" "10" "*" "=c")  stack=()  vars=()
lst='("=b" "10" "*" "=c")  stack=(5)  vars=()
lst='("10" "*" "=c")  stack=(5)  vars=((b 5))
lst='("*" "=c")  stack=(10 5)  vars=((b 5))
lst='("=c")  stack=(50)  vars=((b 5))
lst='()  stack=(50)  vars=((c 50) (b 5))
50

编辑

这是一个使用字符列表的版本。我添加了一个额外的列表 token 来收集要处理的字符。每当需要处理令牌时，我都会将其转换回可接受的字符串。

我还添加了一个辅助函数 cdr0，它非常方便，不会使对 loop 的递归调用完全不可读：

(define (evaluate str)
  (define (cdr0 lst) (if (null? lst) lst (cdr lst))) ; helper: skip one element if the list is not yet empty
  (let loop ((lst (string->list str)) (token '()) (stack '()) (vars  '()))
    (printf "lst=~v  token=~v  stack=~a  vars=~a\n" lst token stack vars) ; display, for debugging purposes
    (cond
      ; end of processing -> return top of stack, we're done
      ((and (null? token) (null? lst)) (car stack))
      ; end of word or end of list -> process
      ((and (or (null? lst) (eqv? (car lst) #\space))
            (not (null? token)))
       (let* ((token-string (list->string (reverse token)))
              (n            (string->number token-string)))  ; try to convert c to a number; returns #f if ko
         (cond
           ; number
           (n
            (loop (cdr0 lst) '() (cons n stack) vars))
           ; variable assignment
           ((string=? (substring token-string 0 1) "=")
            (loop (cdr0 lst) '() stack (cons (list (substring token-string 1) (car stack)) vars)))
           ; multiplication
           ((string=? token-string "*")
            (loop (cdr0 lst) '() (cons (* (first stack) (second stack)) (cddr stack)) vars))
           ; none of these
           (else (error "wot?")))))
      (else
       (loop (cdr lst) (cons (car lst) token) stack vars)))))

测试：

> (evaluate "5 =b 10 * =c")
lst='(# #\space #\= #\b #\space # #[=13=] #\space #\* #\space #\= #\c)  token='()  stack=()  vars=()
lst='(#\space #\= #\b #\space # #[=13=] #\space #\* #\space #\= #\c)  token='(#)  stack=()  vars=()
lst='(#\= #\b #\space # #[=13=] #\space #\* #\space #\= #\c)  token='()  stack=(5)  vars=()
lst='(#\b #\space # #[=13=] #\space #\* #\space #\= #\c)  token='(#\=)  stack=(5)  vars=()
lst='(#\space # #[=13=] #\space #\* #\space #\= #\c)  token='(#\b #\=)  stack=(5)  vars=()
lst='(# #[=13=] #\space #\* #\space #\= #\c)  token='()  stack=(5)  vars=((b 5))
lst='(#[=13=] #\space #\* #\space #\= #\c)  token='(#)  stack=(5)  vars=((b 5))
lst='(#\space #\* #\space #\= #\c)  token='(#[=13=] #)  stack=(5)  vars=((b 5))
lst='(#\* #\space #\= #\c)  token='()  stack=(10 5)  vars=((b 5))
lst='(#\space #\= #\c)  token='(#\*)  stack=(10 5)  vars=((b 5))
lst='(#\= #\c)  token='()  stack=(50)  vars=((b 5))
lst='(#\c)  token='(#\=)  stack=(50)  vars=((b 5))
lst='()  token='(#\c #\=)  stack=(50)  vars=((b 5))
lst='()  token='()  stack=(50)  vars=((c 50) (b 5))
50

如何在 Scheme 中仅使用 1 个列表来构建 2 个列表？

How to build 2 lists using only 1 list in Scheme?

lisp

scheme

functional-programming

rpn

calculator