python用栈实现四则表达式(表达式中包含负数和小数)附全部代码

需求问题

在实际使用过程中,我们会遇到很多需要计算的地方,一般情况下我们使用系统的计算方法就实现:

a = -2.3+((1.0-1.0)/(89.0-1.0)*0.4+0.6)*-5 
print(a) 

输出:-5.3

或者使用eval方法:

a = "-2.3+((1.0-1.0)/(89.0-1.0)*0.4+0.6)*-5"
print(eval(a))

输出:-5.3

上述两种方法都可以算出公式的结果。但是存在一定的限制。例如,如果给出的算式中存在除数为0的情况呢?那上面两种办法就行不通了。
例: (2.0-1.0)/(89.0-89.0)*0.4+0.6,像这样的式子,计算的时候89.0-89.0结果为0,然而这个0又放在了除数的位置,所以就会发生错误。然我们的本身用意是式子中的除数为0的部分为计算结果指定为0,即式子中(2.0-1.0)/(89.0-89.0)该部分结果指定为0,后续的正常计算,那该式子的计算结果最终就等于0.6了。

要想要达到我们这样的目的,那上述的方法就行不通,于是我们就需要自己来实现四则运算。

解决方案

例:-2.3+((1.0-1.0)/(89.0-1.0)*0.4+0.6)*-5,因为我们的需求是式子中可能包含小数,或者负数,在我们人工计算的时候,我们会区分开哪个是整数,哪个是小数,哪个是负数,这样我们才能进行计算;所以我们在用程序计算这个式子的时候,我们也得需要区分开哪个是整数,哪个是小数,哪个是负数,即我们需要将式子转化为:

['-2.3', '+', '(', '(', '1.0', '-', '1.0', ')', '/', '(', '89.0', '-', '1.0', ')', '*', '0.4', '+', '0.6', ')', '*', '-5']

如果按照字符切分的话,那就会将上面的式子切成单个字符,如-2.3被切割成['-', '2', '.', '3'],这样肯定是不对的,切割成这样我们就无法计算了。

所以我们就先要对式子进行切分,切成我们用来计算的列表,就如同这样的式子:

['-2.3', '+', '(', '(', '1.0', '-', '1.0', ')', '/', '(', '89.0', '-', '1.0', ')', '*', '0.4', '+', '0.6', ')', '*', '-5']

然后我们才能进行后续的操作。

第一步:对算式进行切割,得到可以进行计算的列表;
第二步:将公式转化为后缀表达式(用栈实现);
第三步:从左到右依次访问后缀表达式,计算公式结果。

实现步骤

1、 对算式进行切割,得到可以进行计算的列表

def formula_charnge_to_list(formula):
	"""
	:param formula: 需要计算的公式,为全是值的公式,eg: ((1.0-1.0)/(89.0-1.0)*0.4+0.6)*5
	:return: 用于入栈计算的公式列表,负数或者小数被当做一个元素, eg:['(', '(', '1.0', '-', '1.0', ')', '/', '(', '89.0', '-', '1.0', ')', '*', '0.4', '+', '0.6', ')', '*', '5']
	"""
	a_list1 = list(formula.replace(" ", ""))    # 格式化公式,防止公式中的空格影响后续操作
	a_list2 = []    # 存储最终公式列表
	temp_str = ""
	for i in range(len(a_list1)):
		if a_list1[i] in "+*/()":
			if temp_str != "":
				a_list2.append(temp_str)
				temp_str = ""
			a_list2.append(a_list1[i])
		elif a_list1[i].isalnum() or a_list1[i] == ".":
			temp_str += a_list1[i]
		else:
			if i == 0:
				temp_str += a_list1[i]
			else:
				if a_list1[i-1].isalnum() and a_list1[i+1].isalnum():   # 3 - 3
					if temp_str != "":
						a_list2.append(temp_str)
						temp_str = ""
					a_list2.append(a_list1[i])
				elif a_list1[i-1].isalnum() and not a_list1[i+1].isalnum():    # 3 - - 3
					if temp_str != "":
						a_list2.append(temp_str)
						temp_str = ""
					a_list2.append(a_list1[i])
				elif not a_list1[i-1].isalnum() and a_list1[i+1].isalnum():    # 3 + - 3
					temp_str += a_list1[i]
				else:
					continue

		if i == (len(a_list1) - 1) and temp_str != "":
			a_list2.append(temp_str)

	return a_list2


if __name__ == '__main__':
	a = "-2.3 + ( ( 1.0 - 1.0 ) / ( 89.0 - 1.0 ) * 0.4 + 0.6 ) * -5"
	res = formula_charnge_to_list(a)
	print(res)

输出:
['-2.3', '+', '(', '(', '1.0', '-', '1.0', ')', '/', '(', '89.0', '-', '1.0', ')', '*', '0.4', '+', '0.6', ')', '*', '-5']

2、 将中缀表达转化为后缀表达式(用栈实现)

转化规则:从左到右遍历中缀表达式中的每个数字和符号,如果是数字就输出,成为后缀表达式的一部分;若是符号则要分为两种情况讨论:
运算优先顺序是先算括号,后算乘除,最后才是加减。

1)是括号时,如果是左括号:“(”,直接将左括号入栈,如果是右括号:“)”则栈顶元素依次出栈并输出,直到有一个左括号出栈(出栈的左括号不输出到后缀表达式)。

2)是运算符号时,如果栈顶符号为左括号,则直接将这个运算符号入栈。栈顶符号不为左括号时,如果该运算符号优先级比栈顶运算符号高则入栈,比栈顶符号低或者相等时则栈顶元素依次出栈并输出直到栈为空或者栈顶为左括号为止,然后将这个符号入栈。最后将栈顶符号依次出栈并输出,得到的结果即为最终的后缀表达式。

尤其注意在判断时别忘记了判断小数和负数的情况

def change_opt(opt_list):
	result = []  # 结果列表
	stack = []  # 栈
	item_lists = opt_list
	# print(item_lists)
	for item in item_lists:
		# 如果当前字符为整数,小数或者负数(包括负小数),那么直接放入结果列表
		if item.isdigit() or item.split(".")[-1].isdigit() or item.split("-")[-1].split(".")[-1].isdigit():
			result.append(item)
		else:
			if len(stack) == 0:     # 如果栈空,直接入栈
				stack.append(item)
			elif item in '*/(':     # 如果当前字符为*/(,直接入栈
				stack.append(item)
			elif item == ')':
				t = stack.pop()
				while t != '(':
					result.append(t)
					t = stack.pop()
			elif item in '+-' and stack[-1] in '*/':
				if stack.count('(') == 0:
					while stack:
						result.append(stack.pop())
				else:  # 如果有左括号,输出到左括号为止
					t = stack.pop()
					while t != '(':
						result.append(t)
						t = stack.pop()
					stack.append('(')
				stack.append(item)
			else:
				stack.append(item)
	#把栈中数据弹出
	while stack:
		result.append(stack.pop())
	return result

if __name__ == '__main__':
	opt_list = ['-2.3', '+', '(', '(', '1.0', '-', '1.0', ')', '/', '(', '89.0', '-', '1.0', ')', '*', '0.4', '+', '0.6', ')', '*', '-5']
	res = change_opt(opt_list)
	print(res)

输出:
['-2.3', '1.0', '1.0', '-', '89.0', '1.0', '-', '0.4', '*', '/', '0.6', '+', '-5', '*', '+']

3、 从左到右依次访问后缀表达式,计算公式结果

规则:从左到右遍历后缀表达式的每个元素,遇到的是数字就进栈,遇到的是符号就将栈顶的两个数字出栈进行计算,然后将计算结果入栈,最终栈里的值即为计算的结果。

计算时需要注意如果除数为0的情况下,则指定该步计算的结果为0

# 后缀表达式计算
def get_value(follow):
	"""计算公式,得到结果"""
	num = []
	base_opt = ['+', '-', '*', '/']
	# print(follow)
	for j in follow:
		if j.isdigit() or j.split(".")[-1].isdigit() or j.split("-")[-1].split(".")[-1].isdigit():  # 如果是数字(整数,小数,负数或者负小数数),直接入栈
			num.append(float(j))
		if j in base_opt:
			num2 = num.pop()
			num1 = num.pop()
			res = method(num1, num2, j)
			num.append(res)
	return num[0]


def method(num1, num2, j):
	"""计算结果,如果除数为0,则指定该部分计算结果为0,也可以指定为-1等"""
	if j == "+":
		return num1 + num2
	elif j == "-":
		return num1 - num2
	elif j == "*":
		return num1 * num2
	else:
		try:
			res = num1 / num2
			return res
		except Exception as e:
			if "division by zero" in e.__str__():
				return 0
			else:
				raise e


if __name__ == '__main__':
	opt_list = ['-2.3', '1.0', '1.0', '-', '89.0', '1.0', '-', '0.4', '*', '/', '0.6', '+', '-5', '*', '+']
	res = get_value(opt_list)
	print(res)

输出:
-5.3

至此,我们就可以计算出算式中带有小数和负数的稍复杂的这种算式的结果了。

完整代码实现 :

def formula_charnge_to_list(formula):
	"""
	:param formula: 需要计算的公式,为全是值的公式,eg: ((1.0-1.0)/(89.0-1.0)*0.4+0.6)*5
	:return: 用于入栈计算的公式列表,负数或者小数被当做一个元素, eg:['(', '(', '1.0', '-', '1.0', ')', '/', '(', '89.0', '-', '1.0', ')', '*', '0.4', '+', '0.6', ')', '*', '5']
	"""
	a_list1 = list(formula.replace(" ", ""))    # 格式化公式,防止公式中的空格影响后续操作
	a_list2 = []    # 存储最终公式列表
	temp_str = ""
	for i in range(len(a_list1)):
		if a_list1[i] in "+*/()":
			if temp_str != "":
				a_list2.append(temp_str)
				temp_str = ""
			a_list2.append(a_list1[i])
		elif a_list1[i].isalnum() or a_list1[i] == ".":
			temp_str += a_list1[i]
		else:
			if i == 0:
				temp_str += a_list1[i]
			else:
				if a_list1[i-1].isalnum() and a_list1[i+1].isalnum():   # 3 - 3
					if temp_str != "":
						a_list2.append(temp_str)
						temp_str = ""
					a_list2.append(a_list1[i])
				elif a_list1[i-1].isalnum() and not a_list1[i+1].isalnum():    # 3 - - 3
					if temp_str != "":
						a_list2.append(temp_str)
						temp_str = ""
					a_list2.append(a_list1[i])
				elif not a_list1[i-1].isalnum() and a_list1[i+1].isalnum():    # 3 + - 3
					temp_str += a_list1[i]
				else:
					continue

		if i == (len(a_list1) - 1) and temp_str != "":
			a_list2.append(temp_str)

	return a_list2


# 转为后缀表达式,运算表达式元素之间用空格隔开:
def change_opt(opt):
	result = []  # 结果列表
	stack = []  # 栈
	item_lists = formula_charnge_to_list(opt)
	# print(item_lists)
	for item in item_lists:
		# 如果当前字符为整数,小数或者负数(包括负小数),那么直接放入结果列表
		if item.isdigit() or item.split(".")[-1].isdigit() or item.split("-")[-1].split(".")[-1].isdigit():
			result.append(item)
		else:
			if len(stack) == 0:     # 如果栈空,直接入栈
				stack.append(item)
			elif item in '*/(':     # 如果当前字符为*/(,直接入栈
				stack.append(item)
			elif item == ')':
				t = stack.pop()
				while t != '(':
					result.append(t)
					t = stack.pop()
			elif item in '+-' and stack[-1] in '*/':
				if stack.count('(') == 0:
					while stack:
						result.append(stack.pop())
				else:  # 如果有左括号,输出到左括号为止
					t = stack.pop()
					while t != '(':
						result.append(t)
						t = stack.pop()
					stack.append('(')
				stack.append(item)
			else:
				stack.append(item)
	#把栈中数据弹出
	while stack:
		result.append(stack.pop())
	return result


# 后缀表达式计算
def get_value(follow):
	"""计算公式,得到结果"""
	num = []
	base_opt = ['+', '-', '*', '/']
	# print(follow)
	for j in follow:
		if j.isdigit() or j.split(".")[-1].isdigit() or j.split("-")[-1].split(".")[-1].isdigit():  # 如果是数字(整数,小数,负数或者负小数数),直接入栈
			num.append(float(j))
		if j in base_opt:
			num2 = num.pop()
			num1 = num.pop()
			res = method(num1, num2, j)
			num.append(res)
	return num[0]


def method(num1, num2, j):
	"""计算结果,如果除数为0,则指定该部分计算结果为0,也可以指定为-1等"""
	if j == "+":
		return num1 + num2
	elif j == "-":
		return num1 - num2
	elif j == "*":
		return num1 * num2
	else:
		try:
			res = num1 / num2
			return res
		except Exception as e:
			if "division by zero" in e.__str__():
				return 0
			else:
				raise e


if __name__ == '__main__':
	opt = "-2.3+((1.0-1.0)/(89.0-1.0)*0.4+0.6)*-5 "
	postfix_expression = change_opt(opt)
	# print(postfix_expression)
	result = get_value(postfix_expression)
	print(result)
	# 验证(除数为0除外)
	print(eval(opt))

输出:
-5.3
-5.3

参考:利用栈实现四则运算表达式求值,附代码
仅供学习,侵权联删!


版权声明:本文为time_money原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。