中缀表达式转换为前缀表达式(lisp实现)
xsobi 2024-12-22 21:33 1 浏览
使用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 ) )
运行结果如下:
相关推荐
- js向对象中添加元素(对象,数组) js对象里面添加元素
-
一、添加一个元素对象名["属性名"]=值(值:可以是一个值,可以是一个对象,也可以是一个数组)这样添加进去的元素,就是一个值或对象或数组...
- JS小技巧,如何去重对象数组?(一)
-
大家好,关于数组对象去重的业务场景,想必大家都遇到过类似的需求吧,这对这样的需求你是怎么做的呢。下面我就先和大家分享下如果是基于对象的1个属性是怎么去重实现的。方法一:使用.filter()和....
- 「C/C++」之数组、vector对象和array对象的比较
-
数组学习过C语言的,对数组应该都不会陌生,于是这里就不再对数组进行展开介绍。模板类vector模板类vector类似于string,也是一种动态数组。能够在运行阶段设置vector对象的长度,可以在末...
- 如何用sessionStorage保存对象和数组
-
背景:在工作中,我将[{},{}]对象数组形式,存储到sessionStorage,然后ta变成了我看不懂的形式,然后我想取之用之,发现不可能了~记录这次深刻的教训。$clickCouponIndex...
- JavaScript Array 对象 javascript的array对象
-
Array对象Array对象用于在变量中存储多个值:varcars=["Saab","Volvo","BMW"];第一个数组元素的索引值为0,第二个索引值为1,以此类推。更多有...
- JavaScript中的数组Array(对象) js array数组
-
1:数组Array:-数组也是一个对象-数组也是用来存储数据的-和object不同,数组中可以存储一组有序的数据,-数组中存储的数据我们称其为元素(element)-数组中的每一个元素都有一...
- 数组和对象方法&数组去重 数组去重的5种方法前端
-
列举一下JavaScript数组和对象有哪些原生方法?数组:arr.concat(arr1,arr2,arrn);--合并两个或多个数组。此方法不会修改原有数组,而是返回一个新数组...
- C++ 类如何定义对象数组?初始化数组?linux C++第43讲
-
对象数组学过C语言的读者对数组的概念应该很熟悉了。数组的元素可以是int类型的变量,例如int...
- ElasticSearch第六篇:复合数据类型-数组,对象
-
在ElasticSearch中,使用JSON结构来存储数据,一个Key/Value对是JSON的一个字段,而Value可以是基础数据类型,也可以是数组,文档(也叫对象),或文档数组,因此,每个JSON...
- 第58条:区分数组对象和类数组对象
-
示例设想有两个不同类的API。第一个是位向量:有序的位集合varbits=newBitVector;bits.enable(4);bits.enable([1,3,8,17]);b...
- 八皇后问题解法(Common Lisp实现)
-
如何才能在一张国际象棋的棋盘上摆上八个皇后而不致使她们互相威胁呢?这个著名的问题可以方便地通过一种树搜索方法来解决。首先,我们需要写一个函数来判断棋盘上的两个皇后是否互相威协。在国际象棋中,皇后可以沿...
- visual lisp修改颜色的模板函数 怎么更改visual studio的配色
-
(defunBF-yansemokuai(tuyuanyanse/ss)...
- 用中望CAD加载LISP程序技巧 中望cad2015怎么加载燕秀
-
1、首先请加载lisp程序,加载方法如下:在菜单栏选择工具——加载应用程序——添加,选择lisp程序然后加载,然后选择添加到启动组。2、然后是添加自定义栏以及图标,方法如下(以...
- 图的深度优先搜索和广度优先搜索(Common Lisp实现)
-
为了便于描述,本文中的图指的是下图所示的无向图。搜索指:搜索从S到F的一条路径。若存在,则以表的形式返回路径;若不存在,则返回nil。...
- 两个有助于理解Common Lisp宏的例子
-
在Lisp中,函数和数据具有相同的形式。这是Lisp语言的一个重大特色。一个Lisp函数可以分析另一个Lisp函数;甚至可以和另一个Lisp函数组成一个整体,并加以利用。Lisp的宏,是实现上述特色的...
- 一周热门
- 最近发表
- 标签列表
-
- grid 设置 (58)
- 移位运算 (48)
- not specified (45)
- patch补丁 (31)
- strcat (25)
- 导航栏 (58)
- context xml (46)
- scroll (43)
- element style (30)
- dedecms模版 (53)
- vs打不开 (29)
- nmap (30)
- webgl开发 (24)
- parse (24)
- c 视频教程下载 (33)
- android 开发环境 (24)
- paddleocr (28)
- listview排序 (33)
- firebug 使用 (31)
- transactionmanager (30)
- characterencodingfilter (33)
- getmonth (34)
- commandtimeout (30)
- hibernate教程 (31)
- label换行 (33)