检查球拍功能的括号

Question

I'm trying to make a function that takes a non-empty string representing a Racket function and an index of that string. If the index refers to a right parenthesis, then the index of the matching left parentheses is returned. Else false.

> (find-paren "(if (zero? x) (* 2 x) x)" 11)
false
> (find-paren "(if (zero? x) (* 2 x) x)" 12)
4
> (find-paren "(+ (* 2 (- 5 3)) (/ (+ 4 2) 3))" 14)
8
> (find-paren "(+ (* 2 (- 5 3)) (/ (+ 4 2) 3))" 15)
3
> (find-paren "(+ (* 2 (- 5 3)) (/ (+ 4 2) 3))" 30)
0

我正在尝试以尽可能最快的方式完成此操作，因此不会出现爆炸、子字符串、字符串-> 列表、字符串。` 我已经在这个问题上停留了将近一个小时。如果字符串是对称的，那么我的函数将起作用：

(define (find-paren expr i)
  (cond [(not (equal? #\) (string-ref expr i))) false]
        [else (- (string-length expr) i)]))

但它不是对称的。我还创建了一个函数来计算一个字符在字符串中出现的次数，但我不确定它是否有那么多帮助：

(define (char-count c s)
  (local [(define (loop i count)
            (cond
              [(negative? i) count]
              [(char=? c (string-ref s i))
               (loop (sub1 i) (add1 count))]
              [else
               (loop (sub1 i) count)]))]
    (loop (sub1 (string-length s)) 0)))

ISL+

中的任何帮助都会很棒

Answer 1

如果您要使用实际的 Racket 表达式，您迟早需要使用词法分析器将字符串表示形式转换为标记列表。

下面的程序展示了如何找到匹配的左右括号对。给定该列表，很容易找到与给定右括号匹配的左括号。

如果您的解决方案直接作用于字符串表示，则需要模仿 pair-parens-loop 中的算法。

; a TOKEN consists of a lexeme (a 'left, 'right or a char)
; and the position from which the lexeme was read.
(define-struct token (lexeme pos))

; left? and right? checks whether the token was a left or right parenthesis respectively.
(define (left? t)  (eq? (token-char t) 'left))
(define (right? t) (eq? (token-char t) 'right))

; lex : string -> list-of-tokens
;   lex the whole string
(define (lex s)
  (lex-loop s 0))

; lex-loop : string natural -> list-of-tokens
;   lex-loop the part of the string that begins with position p
(define (lex-loop s p)
  (cond
    [(= p (string-length s))        '()]
    [(char=? (string-ref s p) #\()  (cons (make-token 'left p)  (lex-loop s (+ p 1)))]
    [(char=? (string-ref s p) #\))  (cons (make-token 'right p) (lex-loop s (+ p 1)))]
    [else                           (lex-loop s (+ p 1))]))

; pair-parens : list-of-tokens -> list-of-list-of-tokens
;   return a list of mathcing left/right tokens
(define (pair-parens ts)
  (pair-parens-loop ts '() '()))

(define (pair-parens-loop ts pending found)
  (cond
    [(empty? ts) found]
    [(left?  (first ts))
     (pair-parens-loop (rest ts) (cons (first ts) pending) found)]
    [(right? (first ts))
     (pair-parens-loop (rest ts) (rest pending) (cons (list (first pending) (first ts)) found))]
    [else (error)]))


;;;
;;; EXAMPLE
;;;

> (lex "(if (zero? x) (* 2 x) x)")
(list
 (make-token 'left 0)
 (make-token 'left 4)
 (make-token 'right 12)
 (make-token 'left 14)
 (make-token 'right 20)
 (make-token 'right 23))


> (pair-parens (lex "(if (zero? x) (* 2 x) x)"))
(list
 (list (make-token 'left 0) (make-token 'right 23))
 (list (make-token 'left 14) (make-token 'right 20))
 (list (make-token 'left 4) (make-token 'right 12)))

检查球拍功能的括号

Checking parenthesis of racket function

scheme

racket