中缀表达式转换为前缀表达式（lisp实现）

大家好，欢迎来到IT知识分享网。

使用weight、opcode和infix_to_prefix三个函数实现中缀表达式到前缀表达式的转换。

算符优先级函数weight

首先定义函数weight，它返回一个算术运算符（可简称为算符）的优先级（优先权）。

;确定算符的优先权

(defun weight (operator)

(cond

((equal operator ‘dummy) -1) ;运算符号表的开始标记

((equal operator ‘=) 0) ;等于号

((equal operator ‘+) 1) ;加号

((equal operator ‘-) 1) ;减号

((equal operator ‘*) 2) ;乘号

((equal operator ‘/) 2);除号

((equal operator ‘\\) 2);求余运算符

((equal operator ‘^) 3) ;指数运算符

(t (print (list operator ‘not ‘an ‘operator)) ‘nop)

)

)

在有些LISP的实现中，反斜杠“/”表示对下一个字符做特殊处理，如阻止把空格解释为分隔符，所以在上述函数中用双反斜杠“\\”等价地表示单斜杠“\”。

上述函数中的伪运算符dummy用来标记算符表的开端。

算符到操作码的转换函数opcode

定义算符到操作码的转换函数opcode。

;计算与operator对应的lisp函数名.

(defun opcode (operator)

(cond

((equal operator ‘dummy)

(print ‘hit-dummy)

‘dummy

)

((equal operator ‘=) ‘setq)

((equal operator ‘+) ‘plus)

((equal operator ‘-) ‘difference)

((equal operator ‘*) ‘times)

((equal operator ‘/) ‘quotient)

((equal operator ‘\\ ) ‘remainder)

((equal operator ‘^) ‘expt)

(t (print (list operator ‘not ‘an ‘operator)) ‘nop)

)

)

中缀表达式转换为前缀表达式的函数infix_to_prefix

从一种形式到另一种形式的转换方法有多种，这里采用自左向右的线性扫描法。其中，尚未用来产生输出的操作数和运算符都保留在表内。infix_to_prefix函数使用operands和operators两张表分别保存操作数和运算符（操作符）。

;将算术表达式由中缀形式变为前缀形式

(defun infix_to_prefix (ae)

(prog (operands operators) ;操作数表和运算符表

(cond((atom ae) (return ae))) ;特殊情况,只有一个操作数

(setq operators (list ‘dummy)) ;虚拟终结符

stuff ;寻找操作数

(cond

((null ae) 扫描操作数，以运算符结尾

(return ‘unexpected-end)

)

)

;递归

(setq

operands ;操作数入栈

(cons

(cond

((atom (car ae)) (car ae))

(t (infix_to_prefix (car ae)))

)

operands

) ;设置operands

ae (cdr ae) ;删除操作数，设置ae

)

scan ;扫描运算符

(cond

((and(null ae) (equal (car operators) ‘dummy)) ;ae及运算符表为空

(return (car operands)) ;回送结果，operands即为所需的前缀表达式

)

)

(cond

;ae为空或运算符表的第一个算符的优先级高于ae的第一个算符的优先级

((or (null ae)

(not (> (weight (car ae)) (weight (car operators))))) ;嵌套次序.

(setq

operands ;设置operands

(cons (list (opcode (car operators)) (cadr operands) (car operands))

(cddr operands)) ;弹出两个操作数

operators (cdr operators);弹出一个运算符

)

(go scan) ;继续寻找运算符。

)

;否则

(t

(setq

operators (cons (car ae) operators) ; 运算符入栈

ae (cdr ae) ;从ae中删除算符

)

(go stuff)

)

)

)

)

三个函数放在一起

为了便于使用和复制，将三个函数放在一起

;确定算符的优先权

(defun weight (operator)

(cond

((equal operator ‘dummy) -1) ;运算符号表的开始标记

((equal operator ‘=) 0) ;等于号

((equal operator ‘+) 1) ;加号

((equal operator ‘-) 1) ;减号

((equal operator ‘*) 2) ;乘号

((equal operator ‘/) 2);除号

((equal operator ‘\\) 2);求余运算符

((equal operator ‘^) 3) ;指数运算符

(t (print (list operator ‘not ‘an ‘operator)) ‘nop)

)

)

;计算与operator对应的lisp函数名.

(defun opcode (operator)

(cond

((equal operator ‘dummy)

(print ‘hit-dummy)

‘dummy

)

((equal operator ‘=) ‘setq)

((equal operator ‘+) ‘plus)

((equal operator ‘-) ‘difference)

((equal operator ‘*) ‘times)

((equal operator ‘/) ‘quotient)

((equal operator ‘\\ ) ‘remainder)

((equal operator ‘^) ‘expt)

(t (print (list operator ‘not ‘an ‘operator)) ‘nop)

)

)

;将算术表达式由中缀形式变为前缀形式

(defun infix_to_prefix (ae)

(prog (operands operators) ;操作数表和运算符表

(cond((atom ae) (return ae))) ;特殊情况,只有一个操作数

(setq operators (list ‘dummy)) ;虚拟终结符

stuff ;寻找操作数

(cond

((null ae) 扫描操作数，以运算符结尾

(return ‘unexpected-end)

)

)

;递归

(setq

operands ;操作数入栈

(cons

(cond

((atom (car ae)) (car ae))

(t (infix_to_prefix (car ae)))

)

operands

) ;设置operands

ae (cdr ae) ;删除操作数，设置ae

)

scan ;扫描运算符

(cond

((and(null ae) (equal (car operators) ‘dummy)) ;ae及运算符表为空

(return (car operands)) ;回送结果，operands即为所需的前缀表达式

)

)

(cond

;ae为空或运算符表的第一个算符的优先级高于ae的第一个算符的优先级

((or (null ae)

(not (> (weight (car ae)) (weight (car operators))))) ;嵌套次序.

(setq

operands ;设置operands

(cons (list (opcode (car operators)) (cadr operands) (car operands))

(cddr operands)) ;弹出两个操作数

operators (cdr operators);弹出一个运算符

)

(go scan) ;继续寻找运算符。

)

;否则

(t

(setq

operators (cons (car ae) operators) ; 运算符入栈

ae (cdr ae) ;从ae中删除算符

)

(go stuff)

)

)

)

)

在portacle中添加定义，如下图所示：

程序的运行

依次输入命令

(infix_to_prefix ‘(A + B * C) )

(infix_to_prefix ‘(total = principal * ( 1.0 + interest ) ^ years ) )

运行结果如下：