中綴到前綴轉換方案

Question

我想弄清楚如何將中綴表達式轉換爲Scheme中的前綴。

我發現this後，這是我想要的，但在相反的方向。從中綴 - >前綴代替前綴 - >中綴時會發生什麼變化？

編輯：我忘了提及我需要考慮和處理變量。例如，輸入

'(2 + 3 * a^5 + b)

Answer 1

這是相當微不足道的修改鏈接到算法：

(define (infix->prefix lst) 
    (cond 
    ((list? lst) 
    (unless (= 3 (length lst)) (error "not 3 elements")) 
    (let ((operand1 (car lst)) 
      (operator (cadr lst)) 
      (operand2 (caddr lst))) 
     (list operator 
      (infix->prefix operand1) 
      (infix->prefix operand2)))) 
    (else lst))) 

測試：

> (infix->prefix '(1 + 2)) 
'(+ 1 2) 
> (infix->prefix '(1 + (2 * 3))) 
'(+ 1 (* 2 3)) 
> (infix->prefix '((1/4) + (2 * 3))) 
'(+ (/ 1 4) (* 2 3)) 

這並不是雖然通用算法;如果您需要更詳細的內容，請顯示您需要執行的一些轉換示例。

編輯下面是一個例子代碼，更長的表達式的作品，但沒有實現運算符優先級：

(define (infix->prefix lst) 
    (if (list? lst) 
     (if (null? (cdr lst)) 
      ; list with one element -> return element 
      (infix->prefix (car lst)) 
      ; list with more than one element 
      (list (cadr lst) 
       (infix->prefix (car lst)) 
       (infix->prefix (cddr lst)))) 
     ; not a list -> return element 
     lst)) 

測試：

> (infix->prefix '(2 + 3 * a^5 + b)) 
'(+ 2 (* 3 (^ a (+ 5 b))))