1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
| (define (tokenize s) (regexp-match* #px"\\(|[0-9]+|\\+|-|\\*|/|\\(|\\))" s))
(define (parse tokens) (define (parse-expr tokens) (define-values (expr rest-tokens) (parse-term tokens)) (cond [(null? rest-tokens) expr] [(equal? (first rest-tokens) "+") (define-values (rhs rest-tokens2) (parse-expr (rest rest-tokens))) (values `(+ ,expr ,rhs) rest-tokens2)] [(equal? (first rest-tokens) "-") (define-values (rhs rest-tokens2) (parse-expr (rest rest-tokens))) (values `(- ,expr ,rhs) rest-tokens2)] [else (values expr rest-tokens)]))
(define (parse-term tokens) (define-values (expr rest-tokens) (parse-factor tokens)) (cond [(null? rest-tokens) expr] [(equal? (first rest-tokens) "*") (define-values (rhs rest-tokens2) (parse-term (rest rest-tokens))) (values `(* ,expr ,rhs) rest-tokens2)] [(equal? (first rest-tokens) "/") (define-values (rhs rest-tokens2) (parse-term (rest rest-tokens))) (values `(/ ,expr ,rhs) rest-tokens2)] [else (values expr rest-tokens)]))
(define (parse-factor tokens) (cond [(number? (string->number (first tokens))) (values (string->number (first tokens)) (rest tokens))] [(equal? (first tokens) "(") (define-values (expr rest-tokens) (parse-expr (rest tokens))) (when (not (equal? (first rest-tokens) ")")) (error "Expected closing parenthesis")) (values expr (rest rest-tokens))] [else (error "Unexpected token" (first tokens))]))
(first (parse-expr tokens)))
(define (evaluate ast) (cond [(number? ast) ast] [(list? ast) (match ast ['(+ lhs rhs) (+ (evaluate lhs) (evaluate rhs))] ['(- lhs rhs) (- (evaluate lhs) (evaluate rhs))] ['(* lhs rhs) (* (evaluate lhs) (evaluate rhs))] ['(/ lhs rhs) (/ (evaluate lhs) (evaluate rhs))] [else (error "Unknown operation" ast)])] [else (error "Invalid expression" ast)]))
(define (calculate-expression expr) (evaluate (parse (tokenize expr))))
(calculate-expression "(1 + 7) * 13 - 1")
|
tokenize 函数将字符串分解成词法单元,parse 函数构建语法树,evaluate 函数对语法树求值。