这应该是我编程以来完成的难度最大的一个函数了.因为可能存在的情况非常多,需要设计合理的参数来控制解析流程.经验概要:
1.大胆假设一些子功能能够实现,看能否建立整个框架.如果在假设的基础上都无法建立,那么必定需要更换思路.
2.穷举所有可能的情况,想清楚该怎么应对它们.如果写完了整个程序才发现,啊!漏了一种情形.代价或许就是全部推翻重写.
我算是能够理解为什么教科书上推荐设计程序之前要先画流程图,那实际是要求你编程之前要先知道解法,并以一种直观的形式保存.这样,你在将解法翻译为代码时,思路才清晰,效率才高.
什么?难道有人会在不知道解法的情况下就编程?显然有这种人的,我这次就是这样干的.
我这次是吃够了亏.因为我没画流程图.虽然最终完成了,脑海中也终于建立了清晰的逻辑,但这浪费了太多的时间了,这要是在工作中,恐怕不太可能有这么宽松的时间限制.
因此,教训是:复杂问题,想好了解法再编程
---------------------------------------------------------------
前几天写了个解析浮点数运算表达式的ieval函数,后来发现不行,因为还要支持负数啊!
其实负数倒没什么,关键是要支持一元运算符了.比如以下写法都是合法的:
-2
--2
---+++2
-+-+-+2
而且要能够体现一元运算符的优先级仅次于幂运算符这个概念.即:
-2**2 应为-4
(-2)**2 应为4
2--2 应为4
而这个一元运算符刚好和二元运算符的+-是完全相同的字符,只能从它出现的位置来判断是一元还是二元.
总之,感觉是要全部推翻重来了.
果然如此.我整整连续搞到今天才把这个东西写出来.为什么会要这么长的时间呢?原因如下:
- 1.我不知道该用哪些参数来控制函数才好.
我一开始是延续之前的思路,主要用操作符opf进行控制.但写着写着发现它让我思路混乱,我都搞不清自己逻辑是否严密了.
好不容易写出个感觉对的版本,一测发现有些情况会出错.而我根本不想去分析是哪个环节出错.因为太混乱了.
- 2.写了太多的注释.
这让程序变得更加庞大,不好去观察逻辑结构.拉来拉去看的比较痛苦.感觉没必要太早地写注释.
- 3.编程之前没有尝试穷举所有可能的情形,只有在出错或者不知不觉发现还存在其他情形的时候才更加靠近正确解法.
那我怎么又慢慢搞出来了呢?
- 1.大概是"只要功夫深铁杵磨成针",我虽然一开始不知道该用哪些参数来控制才合适,但我却知道哪些参数让我感到混乱和痛苦.我也知道哪些参数实际上没有发挥任何作用,可以删掉.而剩余的参数.就那么几个,试来试去,总会抓到对的.
- 2.在一次又一次的出错中我渐渐形成一个完整的表达式概念:
1)表达式的实质是"值"和"运算符"的集合..好像是废话,但现在感觉很深刻
2)一个表达式的开头字符只可能是:-,+,左括号和浮点数字符
3)在左括号或数字尚未出现之前,-和+必定是一元运算符
4)如果一个完整的数字A之后还存在字符,那么必定是二元运算符opf,而且必定至少跟着另外一个完整的数字B.
5)由于运算符有优先级之分,在没有括号界定的情况下,你解析出了opf和B,也不能立即和A进行二元运算,因为你还需解析B之后的字符情况.
比如1+2*3,A是1,opf是+,B是2,你不能先算1+2,因为*优先级高于+.
而假设出现第三个数字C,你也不能断定它能和B进行运算,因为C之后的字符情况也需要检查.
比如一度让我头疼的一种情况:1+2**2**2**2**2**2
- 3.在遇到"我怎么知道什么时候能够安全地返回B的值呢?"这种情形时,我的直觉认为应该采用递归来解决.以前在理解遍历未知深度的文件夹的原理时,建立了一种"无法确定究竟有多深的时候就用递归"的思考习惯.
结果证明我的直觉是正确的.对于优先级,就是应该用递归来检查.
- 4.先假设存在一些函数来实现我想要的功能,尽量把程序的框架建立起来.比如我做了以下假设:
1)提取括号内的表达式,再计算出值的函数.(wipe_brace)
2)安全返回第二个值和剩余字符串的函数.比如1+2*3+4,安全返回6和剩余字符串+4.(get_safeSec)
3)提取完整值的函数.比如1234.5*2,当检测到1时,就继续检测它后面是不是也是数字,直到碰到*,得出1234.5.(get_Longest_number)
这样做的好处是,你会更快地在形式上完成整个程序.而一旦真的实现了那些假设的函数,那么整个程序就相当于完成了.
当然,这种做法有风险,因为万一那些函数不可能实现,那么建立在它之上的程序也无法实现.
不过,当是在探索一个问题的解法时,我觉得这种做法很合理.
好了,现在开始上源码,作为难度里程碑:
# -*- coding:utf-8 -*- def ieval(s):
"模拟eval函数的浮点数运算"
#不进行正运算,不进行多余的负运算.
#例如'+2-1'视为'2-1'.'---2-1'视为'-2-1'.
binaryDic={'+':float.__add__,
'-':float.__sub__,
'*':float.__mul__,
'/':float.__truediv__,
'%':float.__mod__,
'@':float.__pow__,}#为简化判断,将幂运算符'**'替换为'@'
unaryDic={'-':float.__neg__,
'+':float.__pos__,}
priorDic=dict((('@',3),('*',2),('/',2),('%',2),('+',1),('-',1))) def check(s):
'检测非法字符,删除空格,替换幂操作符'
A=set(s)
B=set('0123456789.+-*/%() ')
assert A<=B,'表达式"%s"包含非法字符:%s.'%\
(s,','.join(map(repr,A-B)))
return s.replace(' ','').replace('**','@')
def get_val(fir='',opf='',sec=''):
'智能求值函数.能进行一元,二元或纯值运算'
if opf:
if sec:
return str(binaryDic[opf](float(fir),float(sec)))
return str(unaryDic[opf](float(fir)))
return fir
def is_float(s):
'判断是否浮点数字符'
return s.isdigit() or s=='.'
def is_prior(firOpf,secOpf):
'判断运算符的优先级'
if secOpf=='@':
return False
return priorDic[firOpf]>=priorDic[secOpf]
def wipe_brace(s,start=0):
's是以左括号开头的字符串'
'此函数将消去括号,求出括号内的值,并返回剩余字符'
pos=s.find(')',start)
if s[1:pos].count('(')==s[1:pos].count(')'):
return s[pos+1:] ,in_eval(s[1:pos])
return wipe_brace(s,pos+1)
def get_Longest_number(s,num=''):
's是以左括号或数字开头的字符串'
'返回s首位开始的最长连续数字串和剩余字符串'
if not s :
return s,num
if s[0]=='(':
return wipe_brace(s)
if is_float(s[0]):
return get_Longest_number(s[1:],num+s[0])
return s,num
def get_safeSec(s,cmpOpf='@',neg='',safeSec='',):
'比较s的第一个二元运算符和cmpOpf的优先级'
'以便获得安全的第二个值'
if not s:
return s,get_val(safeSec,neg)
if not safeSec:
if s[0]=='+':
return get_safeSec(s[1:],cmpOpf,neg)
if s[0]=='-':
return get_safeSec(s[1:],cmpOpf,'' if neg=='-' else '-')
if is_float(s[0]) or s[0]=='(':
rest,safeSec=get_Longest_number(s)
return get_safeSec(rest,cmpOpf,neg,safeSec)
if is_prior(cmpOpf,s[0]):
return s,get_val(safeSec,neg)
rest,safeNum=get_safeSec(s[1:],s[0])
return get_safeSec(rest,cmpOpf,neg,get_val(safeSec,s[0],safeNum)) def in_eval(s='',fir='',opf='',sec=''):
'控制整个解析流程'
if not s:
return get_val(fir,opf,sec)
if not fir:
if s[0]=='-':
return in_eval(s[1:],fir,'' if opf=='-' else '-')
if s[0]=='+':
return in_eval(s[1:],fir,opf)
if is_float(s[0]) or s[0]=='(':
return in_eval(*get_Longest_number(s),opf=opf)
if not sec:
if not opf:
rest,sec=get_safeSec(s[1:],s[0])
return in_eval(rest,fir,s[0],sec)
if s[0]!='@':
return in_eval(s,get_val(fir,opf))
rest,sec=get_safeSec(s[1:])
return in_eval(rest,get_val(fir,'@',sec),opf)
return in_eval(s,get_val(fir,opf,sec))
return in_eval(check(s)) if __name__=='__main__':
test=['1+2*3*4*5+20',
'1+2*3',
'1.1+20.02+300.003',
'-2**2',
'(-2)**2',
'1+2*3**-2**(2-3)*2',
'-2**-2**-2**-2',
'(1+2)*(2+3)/(1-3)',
'((9+3)/2)',
'((1234)-1)',
'1-3*--+++-2**--+++((-2))**--+++-(1-2)**--+++-2*2+1*2**6%9',
'((1+3*(-2)**2)*((2%3+((3+3)*2**3+1))*(1-3)*(1+2)+5*6)*4)']
for x in test:
print('___ '.join([str(s).ljust(20) for s in (ieval(x),eval(x))]))
结果:
>>>
141.0 ___ 141
7.0 ___ 7
321.123 ___ 321.123
-4.0 ___ -4
4.0 ___ 4
3.309401076758503 ___ 3.309401076758503
-0.5582965649524321 ___ -0.5582965649524321
-7.5 ___ -7.5
6.0 ___ 6.0
1233.0 ___ 1233
6.242640687119286 ___ 6.242640687119286
-14352.0 ___ -14352