如何在python的数学表达式中引入额外的括号

Question

我正在进行一个项目，以在python中实现从infix到后缀的转换。

只要表达式完全置于括号内，代码的实现就能工作。它不能处理人类将隐式假定计算顺序的表达式。

例如，我可以使用一个完全括号内的表达式，例如：

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

第二个表达式postorder的输出：

3
6
15
2
3
-
+

第一个(正确)的是：

3
15
+
6
2
3
-
+

Answer 1

免责声明：为您的巨大反应感到抱歉；我很好奇，只是在测试期间为您的问题写下了我所做的事情。在这里找到整个代码：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

这确保我们不会错过表达式中括号所提供的显式分组。同时，当我们计算括号级别时，我们可以发现错误的括号计数所导致的语法错误。

第三步:建立树

为了继续，我们需要从我们的层次结构构建一个实际的二叉树。我们从Step 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))

这里的一些特殊之处是，您也可以使用变量(如我在Step 3中的示例中的示例中的)，但是您必须在计算时将它们映射到实际(未键入的)值：

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) --但是我把这个留给任何想要查看它的人;)

希望它能有所帮助，并为这一巨大的反应感到遗憾。我只是好奇，有一点空闲时间。