中缀到前缀转换方案

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))))