算术表达式分析法大全（其实就三种），算术分析法,tps.py#!/usr
算术表达式分析法大全（其实就三种），算术分析法,tps.py#!/usr
tps.py
#!/usr/bin/env python#-*- coding:utf-8 -*-import re,cmath# 记录运算符的优先级Rgt={'+':2,'-':2,'*':3,'/':3,'^':4}# 预设的变量Par={'x':1,'y':1,'z':1,'i':1,'j':1,'k':1}# 预设的函数，仅限一元函数Fac={'sin':cmath.sin,'cos':cmath.cos,'tan':cmath.tan,'ln':cmath.log}# 运算符的运算映射Cal={'+':lambda x,y:x+y,'-':lambda x,y:x-y,'*':lambda x,y:x*y,'/':lambda x,y:x/y,'^':lambda x,y:x**y}# 数字、函数、变量、运算符的提取All=re.compile('\d+\.\d+[eE][-+]?\d+|\d+\.\d+|[1-9]\d*|[a-zA-Z_]\w*|\^|\+|\-|\*|/|\(|\)')def analyse(str): ''' 这个函数的作用是将字符串解析 ''' str=''.join(str.split()) # 去掉恶心的空格 lst=[] while str: fnd=All.match(str) # 解析出元素 if fnd: lst.append(fnd.group(0)) str=str[fnd.end():] else: # 无法识别元素，算式错误 return [] return lstdef translate(lst): ''' 将列表的成员按类型转化为元组，第一个是标志也是优先级，后一个是实际值 ''' chg=[] for ele in lst: if ele[:1] in '0123456789': # 数字，统一按浮点数计算 chg.append((1,float(ele))) elif ele in Par: # 变量，直接转化为数字了 chg.append((1,Par[ele])) elif ele in Cal: # 运算符，只支持二元运算符 chg.append((Rgt[ele],Cal[ele])) elif ele in Fac: # 函数，只支持一元函数 chg.append((5,Fac[ele])) elif ele=='(': # 左括号 chg.append((0,'(')) elif ele==')': # 右括号 chg.append((6,')')) else: # 匹配不到注册成员，返回空表 return [] return chgdef calc_by_stack(lst): # 共28行 ''' 堆栈法，抑或者逆波兰表达式法，是采用栈的方法 这是自底向上的分析方法，即所谓的LR法 ''' def ClsOpr(opr,ans,tst): # 进行opr的清栈操作 while tst(opr[-1][0]): run=opr.pop() if run[0]==5: # 一元函数，ans栈顶直接操作 ans[-1]=run[1](ans[-1]) else: # 二元运算符，ans栈出俩进一，实际只出了一个 ans[-2]=run[1](ans[-2],ans[-1]) ans.pop() opr,ans=[(0,'(')],[] # 分别作为储存运算符和括号的栈和储存中间值的栈 for i in lst: if i[0]==0: # 左括号直接入opr栈 opr.append(i) elif i[0]==1: # 数字直接入ans栈 ans.append(i[1]) elif i[0]==6: # 右括号，要清栈到左括号 ClsOpr(opr,ans,lambda x:x!=0) opr.pop() else: # 运算符，要先把优先级不低于该算符的清栈后再入栈 ClsOpr(opr,ans,lambda x:x>=i[0]) opr.append(i) ClsOpr(opr,ans,lambda x:x!=0) # 清空opr栈 opr.pop() return ans[0].real # 正确的算式会返回正确的结果，错误的，俺就不知道咧def calc_by_recur(lst): # 共28行 ''' 递归法，或者递归下降法，本质是分治策略，关键在于表达式的切割 基本思想是将算式无副作用的划分为1-2个子算式，求出子算式的值后再做最后的运算 ''' l=len(lst) t,d,i=0,9,0 # 用来记录切割位置、切割位置的优先级、计数 while i<l: if lst[i][0]==0: # 括号内的东西视作一个元素 i,j=i+1,1 while j: i,j=i+1,j+(lst[i][0]==0)-(lst[i][0]==6) i+=1 elif lst[i][0]==1: # 数字视作一个元素 i+=1 if i<l: # 我们要提炼出一个运算符或者函数来切割算式 if d>lst[i][0]: # 这个运算符必然是靠左的，而且是优先级最低的 t,d=i,lst[i][0] i+=1 if d==9: if l==1: # 处理只有一个值的算式 return lst[0][1] elif l>1: # 处理被括号包围的算式 return calc_by_recur(lst[1:-1]) elif d==5: # 这是被函数切割的算式 return lst[0][1](calc_by_recur(lst[1:])).real else: # 被运算符切割的算式 return lst[t][1](calc_by_recur(lst[:t]),calc_by_recur(lst[t+1:])).realdef calc_by_climb(lst): # 共28行 ''' 爬山法，中心思想是按优先级从高到低依次计算 优先进行括号内的计算，当然（小山头？） ''' lst=[(0,'('),]+lst+[(6,')'),] # 为了简化程序，嗯，用无副作用的方式 while len(lst)>1: i,j=0,0 while lst[i][0]!=6: # 为了选出一个内部不含嵌套括号的括号，嗯 if lst[i][0]==0:j=i i+=1 son=lst[j+1:i] # 选出来作为子列表 while 1: k,d,t=0,0,0 for k in range(len(son)): if d<son[k][0]: # 对于木有括号的子算式，我们选出优先级最高的运算 t,d=k,son[k][0] if d==5: # 这里要进行定点清除元素的操作，一元函数版本 son[t]=(1,son[t][1](son[t+1][1]).real) son.pop(t+1) elif d>1: # 进行定点清除，二元算符版 son[t]=(1,son[t][1](son[t-1][1],son[t+1][1]).real) son.pop(t-1) son.pop(t) else: #这就是说，括号内只有一个数字了 break lst=lst[:j]+son+lst[i+1:] return lst[0][1]if __name__ == '__main__': lst=analyse('4-2*(3+5)') print lst lst=translate(lst) print lst print calc_by_stack(lst) print calc_by_recur(lst) print calc_by_climb(lst)MyDeco.py
def track(func): def dec(x): if type(x)==type(''):return '\''+x+'\'' return str(x) def _track(*lst,**dic): t=0 print '%s('%func.__name__, if lst: for i in lst: if t: t=1 print ',', print dec(i), if dic: for i,j in dic.items(): if t: t=1 print ',', print dec(i),'->',dec(j), print ')' return func(*lst,**dic) return _trackdef record(func): import time def _record(*lst,**dic): print time.asctime(),'call',func__name__ return func(*lst,**dic) return _recordtps2.py
#!/usr/bin/env python#-*- coding:utf-8 -*-import re,cmathfrom MyDeco import track# 记录运算符的优先级Rgt={'+':1,'-':1,'*':2,'/':2,'^':3}# 预设的变量Par={'x':1,'y':1,'z':1,'i':1,'j':1,'k':1}# 预设的函数，仅限一元函数Fac={'sin':cmath.sin,'cos':cmath.cos,'tan':cmath.tan,'ln':cmath.log}# 运算符的运算映射Cal={'+':lambda x,y:x+y,'-':lambda x,y:x-y,'*':lambda x,y:x*y,'/':lambda x,y:x/y,'^':lambda x,y:x**y}# 数字、函数、变量、运算符的提取All=re.compile('\d+\.\d+[eE][-+]?\d+|\d+\.\d+|[1-9]\d*|[a-zA-Z_]\w*|\^|\+|\-|\*|/|\(|\)')@trackdef analyse(str): ''' 这个函数的作用是将字符串解析 ''' str=''.join(str.split()) # 去掉恶心的空格 lst=[] while str: fnd=All.match(str) # 解析出元素 if fnd: lst.append(fnd.group(0)) str=str[fnd.end():] else: # 无法识别元素，算式错误 return [] return lst@trackdef calc_by_stack(lst): # 共32行 ''' 堆栈法，抑或者逆波兰表达式法，是采用栈的方法 这是自底向上的分析方法，即所谓的LR法 ''' def ClsOpr(opr,ans,tst): # 进行opr的清栈操作 while tst(opr[-1][0]): run=opr.pop() if run[0]==4: # 一元函数，ans栈顶直接操作 ans[-1]=run[1](ans[-1]).real else: # 二元运算符，ans栈出俩进一，实际只出了一个 ans[-2]=run[1](ans[-2],ans[-1]) ans.pop() opr,ans=[(0,'(')],[] # 分别作为储存运算符和括号的栈和储存中间值的栈 for i in lst: if i=='(': # 左括号直接入opr栈 opr.append((0,i)) elif i[:1] in '0123456789': # 数字直接入ans栈 ans.append(float(i)) elif i in Par: # 变量直接入ans栈 ans.append(Par[i]) elif i in Fac: # 函数右结合，优先级又最高，故直接入opr栈 opr.append((4,Fac[i])) elif i in Cal: # 运算符左结合，要先把优先级不低于该算符的清栈后再入栈 j=Rgt[i] ClsOpr(opr,ans,lambda x:x>=j) opr.append((j,Cal[i])) elif i==')': # 右括号，要清栈到左括号 ClsOpr(opr,ans,lambda x:x!=0) opr.pop() ClsOpr(opr,ans,lambda x:x!=0) # 清空opr栈 return ans[0] # 正确的算式会返回正确的结果，错误的，俺就不知道咧@trackdef calc_by_recur(lst): # 共32行 ''' 递归法，或者递归下降法，本质是分治策略，关键在于表达式的切割 基本思想是将算式无副作用的划分为1-2个子算式，求出子算式的值后再做最后的运算 ''' l=len(lst) t,d,i=0,9,0 # 用来记录切割位置、切割位置的优先级、计数 while i<l: if lst[i]=='(': # 括号内的东西视作一个元素 i,j=i+1,1 while j: i,j=i+1,j+(lst[i]=='(')-(lst[i]==')') i+=1 elif lst[i][:1] in '0123456789' or lst[i] in Par: # 数字或变量 i+=1 if i<l: # 我们要提炼出一个运算符或者函数来切割算式 if lst[i] in Cal:j=Rgt[lst[i]] elif lst[i] in Fac:j=4 else:j=0 if d>j:t,d=i,j # 这个运算符必然是靠左的，而且是优先级最低的 i+=1 if d==9: if l==1: if lst[0] in Par: # 处理只有一个值的算式 return Par[lst[0]] else: return float(lst[0]) elif l>1: # 处理被括号包围的算式 return calc_by_recur(lst[1:-1]) elif d==4: # 这是被函数切割的算式 return Fac[lst[0]](calc_by_recur(lst[1:])).real else: # 被运算符切割的算式 return Cal[lst[t]](calc_by_recur(lst[:t]),calc_by_recur(lst[t+1:]))#@trackdef calc_by_climb(lst): # 共31行 ''' 爬山法，中心思想是按优先级从高到低依次计算 优先进行括号内的计算，当然（小山头？） ''' lst=['(',]+lst+[')',] # 为了简化程序，嗯，用无副作用的方式 while len(lst)>1: i,j=0,0 while lst[i]!=')': # 为了选出一个内部不含嵌套括号的括号，嗯 if lst[i]=='(':j=i i+=1 son=lst[j+1:i] # 选出来作为子列表 while 1: d,t=0,0 for k in range(len(son)): # 对于木有括号的子算式，我们选出优先级最高的运算 if son[k] in Cal: if d<Rgt[son[k]]:t,d=k,Rgt[son[k]] elif son[k][:1] in '0123456789':son[k]=float(son[k]) elif son[k] in Par:son[k]=Par[son[k]] elif son[k] in Fac:t,d=k,4 if d==4: # 这里要进行定点清除元素的操作，一元函数版本 son[t]=str(Fac[son[t]](son[t+1]).real) son.pop(t+1) elif d: # 进行定点清除，二元算符版 son[t]=str(Cal[son[t]](son[t-1],son[t+1])) son.pop(t-1) son.pop(t) else: #这就是说，括号内只有一个数字了 break lst=lst[:j]+son+lst[i+1:] return lst[0]if __name__ == '__main__': lst=analyse('47+677') print calc_by_climb(lst)相关内容
- 纯Python实现的DES加解密算法，pythondes解密算法,test_pyd
- AES加密，,[Python]代码fr
- 猜数游戏，猜数,[Python]代码de
- python抓取网页及网页上所有连接的演示代码，python抓取
- 查单词的脚本，单词脚本,#!/usr/bin/p
- Python xml和xsl转换为html，pythonxmlxslhtml,用的libxml2，所以
- 创建并修改excel，创建修改excel,[Python]代码#创
- python分页类，python分页,python分页类#co
- 简单验证码识别，验证码识别,get_CAPTCHA.
- 下载豆瓣音乐小站歌曲，豆瓣小站歌曲,[Python]代码#!
评论关闭