我正在一个项目中，以在python中实现从infix到postfix的转换。
只要将表达式完全放在方括号中，代码的实现就起作用。它无法处理人类会隐式承担计算顺序的表达式。
例如，我可以使用全括弧表达式，例如：
((3+15)*2)+(6-3)
并获得正确的结果。
但是，人类通常可以这样写：
(3+15)*2+(6-3)
假设使用第一个外部括号。
是否有任何算法可以正确添加方括号。如果没有，是否存在解决此类问题的最佳实践解决方案？
更新：
这是解析树函数的实现：
class BinaryTree:
def __init__(self, root):
self.key = root
self.left_child = None
self.right_child = None
def insert_left(self, new_node):
if self.left_child == None:
self.left_child = BinaryTree(new_node)
else:
t = BinaryTree(new_node)
t.left_child = self.left_child
self.left_child = t
def insert_right(self, new_node):
if self.right_child == None:
self.right_child = BinaryTree(new_node)
else:
t = BinaryTree(new_node)
t.right_child = self.right_child
self.right_child = t
def get_right_child(self):
return self.right_child
def get_left_child(self):
return self.left_child
def set_root_val(self, obj):
self.key = obj
def get_root_val(self):
return self.key
def build_parse_tree(fp_exp):
fp_list = re.findall('[+-/*//()]|\d+', fp_exp)
p_stack = Stack()
e_tree = BinaryTree('')
p_stack.push(e_tree)
current_tree = e_tree
for i in fp_list:
if i == '(':
current_tree.insert_left('')
p_stack.push(current_tree)
current_tree = current_tree.get_left_child()
elif i not in ['+', '-', '*', '/', ')']:
current_tree.set_root_val(int(i))
parent = p_stack.pop()
current_tree = parent
elif i in ['+', '-', '*', '/']:
current_tree.set_root_val(i)
current_tree.insert_right('')
p_stack.push(current_tree)
current_tree = current_tree.get_right_child()
elif i == ')':
current_tree = p_stack.pop()
else:
raise ValueError
return e_tree
def postorder(tree):
if tree != None:
postorder(tree.get_left_child())
postorder(tree.get_right_child())
print (tree.get_root_val())
第二个表达式后置命令的输出：
3
6
15
2
3
-
+
第一个（正确）的是：
3
15
+
6
2
3
-
+
最佳答案
免责声明：很抱歉得到如此巨大的回应；我很好奇，只是写下了我在测试中为您的问题做了些什么。在此处找到完整的代码：https://gist.github.com/jbndlr/3657fa890539d29c9e4b0311dc60835d
顺便说一句，这只是测试代码，不能用于生产环境，因为它可能仍然存在缺陷。
响应
按下空字符串的顺序解析和树设置似乎有些奇怪，但我无法准确指出您的错误。您的解析以某种方式吞没了*运算符，可能是因为其左元素是一个右括号。
在进行一些尝试时，我尝试重现并提出了一种解决方案，该解决方案可以正确解析简单的方程式并可以生成所需的括号。即使不再需要，如果树已经被正确解析，您也可以使用它来生成完全包围的方程式，或者根据自己的需要对其进行扩展。
准备：进口
from __future__ import print_function
import re
步骤1：标记输入
此函数将字符串用作表达式，并生成表示令牌的元组列表。它还已经将它们归类为一种简单（以字符串表示）的类型，以供以后处理。
def tokenize(expression):
'''Generate tokens from a string following fixed rules.
'''
scanner = re.Scanner([
(r'[0-9]\.[0-9]+', lambda _, t: ('FLOAT', t)),
(r'[0-9]+', lambda _, t: ('INTEGER', t)),
(r'[a-z_]+', lambda _, t: ('IDENTIFIER', t)),
(r'\(', lambda _, t: ('P_OPEN', t)),
(r'\)', lambda _, t: ('P_CLOSE', t)),
(r'[+\-*/]', lambda _, t: ('OPERATOR', t)),
(r'\s+', None),
])
tokens, _ = scanner.scan(expression)
return tokens
到目前为止，这种方法还不完整，但是足以说明构建二进制分析树。注意规则的顺序很重要；这没有什么区别，因为我没有捕捉到单个点，但是将
INTEGER放在FLOAT之前可能会使以后混乱。步骤2：解析层次结构
下一个函数获取步骤1中生成的标记列表，并将放在方括号中的所有部分作为单独的子列表解析。结果是一个嵌套列表，其中每个先前放在方括号中的部分都移到了更深的层次。
def parse(tokens, in_parens=False):
'''Parse a list of tokens that may contain brackets into a token hierarchy
where all brackets are removed and replaced by list nesting.
'''
cur = []
i = 0
while i < len(tokens):
t = tokens[i]
if t[0] == 'P_OPEN':
# If we hit an opening bracket, we memorize its position and search
# for the corresponding closing one by counting the stacked
# brackets.
pos_open = i
pos_close = None
par_stack = 0
for j, p in enumerate(tokens[i:]):
if p[0] == 'P_OPEN':
# Deeper nesting, increase.
par_stack += 1
elif p[0] == 'P_CLOSE':
# Level closed, decrease.
par_stack -= 1
if par_stack == 0:
# If we hit level 0, we found the corresponding closing
# bracket for the opening one.
pos_close = i + j
break
if pos_close is None:
# If we did not find a corresponding closing bracket, there
# must be some syntax error.
raise Exception('Syntax error; missing closing bracket.')
# For the bracketed subset we just found, we invoke a recursive
# parsing for its contents and append the result to our hierarchy.
elem = parse(tokens[i + 1:j], in_parens=True)
cur.append(elem)
i = j
elif t[0] == 'P_CLOSE':
if not in_parens:
# If we hit a closing bracket but are not searching for one, we
# found too many closing brackets, which is a syntax error.
raise Exception('Syntax error; too many closing brackets.')
return cur
else:
cur.append(t)
i += 1
return cur
这确保了我们不会错过表达式中括号中给出的显式分组。同时，在计算括号级别时，我们可以发现由错误的括号计数导致的语法错误。
步骤3：建树
为了继续进行，我们需要根据层次结构构建一个实际的二叉树。从第2步获得的层次结构中，所有未加括号的链式运算符仍处于同一级别，因此我们尚不知道运算符的执行顺序。这就是现在解决的问题。
从
Node（即令牌的嵌套列表）创建新的hierarchy时，我们搜索了一个可用作当前构建的Node运算符的数据透视元素。我们选择最弱的绑定运算符，因为我们是自上而下构建树的，但它会自下而上进行评估。因此，最后要执行的操作是我们希望在树的最高Node中执行的操作。class Node(object):
def __init__(self, hierarchy, parent=None):
if len(hierarchy) == 1 and type(hierarchy[0]) is list:
hierarchy = hierarchy[0] # Bracketed descent
# Find position of operator that has the weakest binding priority and
# use it as pivot element to split the sequence at. The weakest binding
# is executed last, so it's the topmost node in the tree (which is
# evaluated bottom-up).
pivot = self._weakest_binding_position(hierarchy)
if pivot is not None:
self.left = Node(hierarchy[:pivot], parent=self)
self.op = hierarchy[pivot][1]
self.right = Node(hierarchy[pivot + 1:], parent=self)
else:
# There is no pivot element if there is no operator in our
# hierarchy. If so, we hit an atomic item and this node will be
# a leaf node.
self.value = hierarchy[0]
def _binding_order(self, operator):
'''Resolve operator to its binding order.'''
if operator in '+-':
return 1
elif operator in '*/':
return 2
raise Exception('Parsing error; operator binding cannot be assessed.')
def _weakest_binding_position(self, tokens):
'''Return position of operator with weakest binding (maintains LTR).'''
ops = sorted([
(i, self._binding_order(t[1]))
for i, t in enumerate(tokens)
if t[0] == 'OPERATOR'
], key=lambda e: e[1], reverse=True)
if len(ops) == 0:
if len(tokens) != 1:
raise Exception('Parsing error; found sequence w/o operator.')
return None
return ops[-1][0]
def isleaf(self):
if hasattr(self, 'value'):
return True
return False
def __str__(self):
if self.isleaf():
return str(self.value[1])
else:
return '({:s} {:s} {:s})'.format(self.left, self.op, self.right)
如果要查看树的设置方式，只需在
print(self)末尾的Node.__init__()。这将使您自底向上打印所有节点。我在
Node.__str__()方法中添加了一些括号，以根据输入内容实际制作一个完全包围的表达式。您可以使用以下示例进行验证：if __name__ == '__main__':
expressions = [
'(3+15)*2+6-3',
'(a+15)*2+6/3'
]
for expr in expressions:
root = Node(parse(tokenize(expr)))
print(root)
...产量
>>> ((((3 + 15) * 2) + 6) - 3)
>>> (((a + 15) * 2) + (6 / 3))
因此，如果您现在想以后缀表示法打印（或返回）此代码，则可以通过在
Node.__str__()方法中更改此行来切换运算符和操作数：<<<<<<<<
return '({:s} {:s} {:s})'.format(self.left, self.op, self.right)
======
return '({:s} {:s} {:s})'.format(self.left, self.right, self.op)
>>>>>>>>
如果您希望返回后缀表示法以进行进一步处理，而不是仅仅以字符串形式获取它，则只需编写另一个方法（警告：伪代码）：
def postfix(self):
if self.isleaf():
return self.value
else:
return (self.left.postfix(), self.right.postfix(), self.op)
然后从您的
root节点调用它：pf = root.postfix()
步骤4：评估
最后，可以将方法放入
Node类以评估表达式。此方法检查我们是否具有叶节点，如果有，则使用正确的类型返回其值。否则，它将评估其左子项和右子项，并应用所需的运算符，然后将结果向上传递到树上。def eval(self, variables={}):
if self.isleaf():
ttype, value = self.value
if ttype == 'FLOAT':
return float(value)
elif ttype == 'INTEGER':
return int(value)
elif ttype == 'IDENTIFIER':
if value in variables.keys():
return variables[value]
else:
raise Exception('Unbound variable: {:s}'.format(value))
else:
raise Exception('Unknown type: {:s}'.format(ttype))
else:
left = self.left.eval(variables=variables)
right = self.right.eval(variables=variables)
if self.op == '+':
return left + right
elif self.op == '-':
return left - right
elif self.op == '*':
return left * right
elif self.op == '/':
return left / right
else:
raise Exception('Unknown operator: {:s}'.format(self.op))
这里有一些特殊的事情，您还可以使用变量（例如在第3步中的示例中的
a），但是您必须将它们映射到求值时的实际（非类型化）值：if __name__ == '__main__':
expression = '(a+15)*2+6/3'
tokens = tokenize(expression)
hierarchy = parse(tokens)
root = Node(hierarchy)
print(root)
print(root.eval({'a': 7}))
...产量：
>>> (((a + 15) * 2) + (6 / 3))
>>> 46
最后的想法
如前所述，这远非完美。我什至注意到，它以某种方式无法解析表达式，其中单个运算符将两个包围在方括号中的部分（如
(1-2)/(0+5)）连接在一起-但我将其留给想要查看它的人使用；）希望它能有所帮助；对于这个巨大的回应深表歉意。我只是好奇，有一点闲暇时间。
关于python - 如何在python的数学表达式中引入额外的括号，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48563175/