事先说明
python中已经有eval() 函数用于实现字符串公式求值功能。
看了一点《编译原理》，突然有了想实现这么一个功能的想法!（之前也尝试过，但没有成功写出代码）
本文求解
仅支持四则运算
{
+
,
?
,
?
,
/
}
\{+, -, *, /\}
{+,?,?,/}和括号{(,)}，且忽略空格的影响。如果想支持幂运算等操作也可自己弄懂代码之后自行添加。本代码已经经过某些公式字符串的验证，并且能成功求解。如若大家发现bug，可与我联系。
词分析
例如
"
1
+
28
?
(
2
+
5
)
/
5
?
114
/
(
100
+
200
?
100
)
?
3343
/
323
"
"1 + 28 * (2 + 5 ) / 5 * 114 / (100 + 200 - 100) * 3343 / 323"
"1+28?(2+5)/5?114/(100+200?100)?3343/323"。因为它是一个个字符组成的，我首先将它合成一个个操作符或者数字。输出如下：
[
′
1
′
,
′
+
′
,
′
2
8
′
,
′
?
′
,
[
′
2
′
,
′
+
′
,
′
5
′
]
,
′
/
′
,
′
5
′
,
′
?
′
,
′
11
4
′
,
′
/
′
,
[
′
10
0
′
,
′
+
′
,
′
20
0
′
,
′
?
′
,
′
10
0
′
]
,
′
?
′
,
′
334
3
′
,
′
/
′
,
′
32
3
′
]
['1', '+', '28', '*', ['2', '+', '5'], '/', '5', '*', '114', '/', ['100', '+', '200', '-', '100'], '*', '3343', '/', '323']
[′1′,′+′,′28′,′?′,[′2′,′+′,′5′],′/′,′5′,′?′,′114′,′/′,[′100′,′+′,′200′,′?′,′100′],′?′,′3343′,′/′,′323′]
解析树
根据“词分析”的生成解析树的形式，结果返回解析树的根节点。
后序优先遍历
根据生成的解析树，采用后序优先遍历求解。
代码Code
from collections import deque
class Node:
def __init__(self, operator, value):
self.operator = operator
self.value = value
self.lchild = None
self.rchild = None
def operator_(operator, left, right):
if operator == "+":
return left + right
if operator == "-":
return left - right
if operator == "*":
return left * right
if operator == "/":
return left / right
def postOrder(node, deque):
if node == None:
return
postOrder(node.lchild, deque)
postOrder(node.rchild, deque)
if node.operator:
right = deque.pop()
left = deque.pop()
deque.append(operator_(node.value, left, right))
else:
deque.append(node.value)
class Formula:
def __init__(self, formula_str):
self.formula_str = formula_str
self.node = None
self.operator = ["+", "-", "*", "/"]
self.prior = ["*", "/"]
self.noprior = ["+", "-"]
self.neglect = [" "]
self.word_list = self.word_analyse(self.formula_str)
def word_analyse(self, process_str):
word_list = []
if process_str == "":
return word_list
start = 0
while start < len(process_str):
c = process_str[start]
if c in self.operator:
word_list.append(c)
start += 1
elif c == "(":
end = start + 1
count = 1
while end < len(process_str) and count != 0:
if process_str[end] == "(":
count += 1
elif process_str[end] == ")":
count -= 1
end += 1
if count != 0:
raise SyntaxError("正反括号不匹配")
word_list.append(Formula.word_analyse(self, process_str[start + 1: end - 1]))
start = end + 1
elif c.isdigit():
digit_c = ""
while start < len(process_str) and process_str[start].isdigit():
digit_c += process_str[start]
start += 1
word_list.append(digit_c)
elif c in self.neglect:
start += 1
else:
raise SyntaxError("表达式错误")
return word_list
def sentence_analyse(self, word_list):
root_node = None
if len(word_list) == 0:
return root_node
index = 0
while index < len(word_list):
word = word_list[index]
if word in self.operator:
node = Node(True, word)
if root_node == None:
raise SyntaxError("表达式错误")
node.lchild = root_node
if word in self.noprior:
end = index + 1
while end < len(word_list) and word_list[end] not in self.noprior:
end += 1
if index + 1 == end:
raise SyntaxError("表达式错误")
node.rchild = Formula.sentence_analyse(self, word_list[index + 1: end])
index = end
root_node = node
elif word in self.prior:
index += 1
if index == len(word_list):
raise SyntaxError("表达式错误")
node.rchild = Formula.sentence_analyse(self, word_list[index:index+1])
root_node = node
index += 1
elif isinstance(word, list):
root_node = Formula.sentence_analyse(self, word)
index += 1
else:
if root_node != None:
raise SyntaxError("表达式错误")
root_node = Node(False, float(word))
index += 1
return root_node
def calu_formula_str(self):
root_node = self.sentence_analyse(self.word_analyse(self.formula_str))
deque_ = deque([])
postOrder(root_node, deque_)
return deque_.pop()
if __name__ == "__main__":
formula = Formula("1 + 28 * (2 + 5 ) / 5 * 114 / (100 + 200 - 100) * 3343 / 323")
print(formula.word_analyse(formula.formula_str))
print(formula.calu_formula_str())
|