I am trying to do a function that takes a list of characters as input, and returns a list that contains all the characters before a specific character given in a condition, so that I can evaluate a postfix expression.
Example: the user enters the string " 5 =b 10 * =c "
First step I do is to convert this string to a list using string->list, so I get a list like this
(#\5 #\space #\=#\b #\space #\10 #\space #\* #\space #\=#\c #\space)
Then I start reading the list and I stop once I read the character #\=, and I put all the characters before it in a list1, and then all what's after the character in list2.
So I get list1 (#\5) and list2 is (#\b #\space #\10 #\space #\* #\space #\=#\c #\space)
And I assign the 5 to the b which is the (car list2), then continue reading list2 until I read another =, then I put all the elements before the second = in a list which is (#\b #\space #\10 #\space #\*) in a list, then I calculate b * 10 , and stock the result in c which is the first element of the last list.
I wrote this function
(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)))))
but it seems like it is not really what I want and everything is getting more complicated... Any idea? Just suggest an idea how to solve such a problem.
You don't mention which implementation you're using so I'll go with Racket which is what I am most familiar with.
Some remarks:
I created a working implementation using a named let which is the looping construct that I would use here. I am also using let* and a few handy procedures from Racket like substring and string-split. I don't know if you are allowed to use those but you can always create them yourself.
So here is an example implementation which is neither complete nor fool-proof but it correctly processes your example input:
(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))))))
The display will show you the intermediary results:
> (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
EDIT
Here's a version using a list of chars. I have added an additional list token which collects the chars to be processed. Whenever a token needs to be processed I'm converting it back to a string which should be acceptable.
I have also added a helper function cdr0 which is incredibly handy in order not to make the recursive calls to loop completely unreadable:
(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)))))
Testing:
> (evaluate "5 =b 10 * =c")
lst='(#\5 #\space #\= #\b #\space #\1 #\0 #\space #\* #\space #\= #\c) token='() stack=() vars=()
lst='(#\space #\= #\b #\space #\1 #\0 #\space #\* #\space #\= #\c) token='(#\5) stack=() vars=()
lst='(#\= #\b #\space #\1 #\0 #\space #\* #\space #\= #\c) token='() stack=(5) vars=()
lst='(#\b #\space #\1 #\0 #\space #\* #\space #\= #\c) token='(#\=) stack=(5) vars=()
lst='(#\space #\1 #\0 #\space #\* #\space #\= #\c) token='(#\b #\=) stack=(5) vars=()
lst='(#\1 #\0 #\space #\* #\space #\= #\c) token='() stack=(5) vars=((b 5))
lst='(#\0 #\space #\* #\space #\= #\c) token='(#\1) stack=(5) vars=((b 5))
lst='(#\space #\* #\space #\= #\c) token='(#\0 #\1) 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