算术表达式分析法大全代码,Python代码库,德仔网

代码语言

代码分类

【Python】算术表达式分析法大全

作者:Foyon / 发布于2012/11/13/ 875

共三种分析算数表达式的方法，其实还有一个变种，不过都是这三种法子衍生出来的，不知道还有木有其它的法子。这三个，都支持函数（限一元函数）、运算符（限二元运算符）、变量，也可以很方便的扩展为支持其它函数和运算符的。 tps是原版，tps2是为了更形象化，把转化步骤嵌入计算函数的版本，配合MyDeco可以演示一下递归啥的。

#!/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 lst

def 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 chg

def 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:])).real

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

试试其它关键字

　算术表达式　

同语言下

可能有用的

Foyon贡献的其它代码(3)