如何去除数学表达式中的无用括号

最近工作上遇到了这个问题，挺有意思，终于遇到了一些有点意思的东西，于是深入研究了下。

问题背景

问题大概背景是 系统中会展示数学公式，公式是用树来表达的，以运算符号为节点，比如 3=1+2，首先根节点是=，然后左子节点为3，右子节点是+，接下来+的左子节点是1，右子节点是2，就是以这种方式来表示一个数学公式。

然后展示的时候并不知道哪些地方要加括号，因为括号这个信息隐藏在树里了，展示的时候只能是每个操作符的两边都加上括号，这样展示出来就非常繁琐，那么就得想一个算法来将这些无用括号去除掉。

算法描述

算法大概是这样的，只要括号内的非括号部分的数学符号的最小优先级小于括号任意一边数学符号的优先级，那么括号就是必须的，否则就是无用的括号。

比如q * (a * b + c * d) + c，括号内部的+和*，最小优先级是+，括号两边是*和+，小于其中一个*的优先级，那么这个括号就是必须的。

同理，q * (a * b * c * d) + c，这个括号就是无用的。

原理就是括号里面的优先级如果都是高于括号两边，那么不加括号，也是会先计算括号里面的运算。

另外为啥是非括号部分，因为内部如果已经有括号了，那么子括号肯定是先运算了，可以把这个子括号当一个整体对待。

当然目前还有一个问题，就是遇到/和-的时候会有一些问题，比如a/(b/c)或者a-(b-c)，主要原因是/和-有取反的作用，所以需要特殊处理：也就是如果/和-右侧的括号需要保留。

代码实现

回到问题背景，按照这样的数据结构，其实算是简化了。结点都是运算符，那么如果把结点左侧作为括号包裹的内容，只需要比较结点左侧的非括号部分最小优先级和结点符号优先级就可以了。同理，右侧也是一样的。

而且针对/和-的特殊处理也更简单了，只需要判断结点运算符是不是/和-，如果是，那么右侧部分需要加括号，当然如果需要的话。

另外代码还实现了一个功能：小括号，中括号，大括号的嵌套。主要原理就是如果某个结点需要加括号，那么递归的去找一下左节点和右节点目前使用的最大括号，在此基础上再用更高一级的括号。

实现代码大概如下：

class BracketProcessor:
    small_bracket = 'small'
    middle_bracket = 'middle'
    big_bracket = 'big'
    priority_default = 3
    operator_priority = {
        '+': 1,
        '-': 1,
        '*': 2,
        '/': 2,
    }

    def __init__(self, formula_items, expression):
        self.formula_items = formula_items
        self.expression = expression
        self.formula_dict = self.get_formula_dict(formula_items)
        self.start_node = self.get_start_node(self.formula_dict)
        self.brackets = {
            self.small_bracket: 0,
            self.middle_bracket: 1,
            self.big_bracket: 2
        }

    @classmethod
    def get_formula_dict(cls, formula_items):
        formula_dict = {}
        for item in formula_items:
            origin = item.data['origin']
            if 'left' not in origin and 'node' in origin:
                origin.update(origin['node'])
            if 'name' not in origin:
                origin['name'] = origin['operator']
            formula_dict[origin['index']] = item
        return formula_dict

    @classmethod
    def get_start_node(cls, formula_dict):
        for key, value in formula_dict.items():
            if value.data['origin']['name'] == '=':
                left_node = formula_dict.get(value.data['origin']['left'])
                right_node = formula_dict.get(value.data['origin']['right'])
                return left_node if left_node.data['origin'].get('operator') else right_node
        return None

    def process(self):
        if self.expression and '(' not in self.expression:
            return
        # 搜索 left 和 right 的最低优先级 X，Y，
        # 如果 X 优先级小于 start_node 的优先级，那么 X 需要括号
        # 否则，不需要括号
        # 对于 Y 同理
        # 只在一个分支上检查level
        # 特例 / - 右边分支如果有同级的 需要带括号
        # 括号内部 非括号部分的优先级
        self.fill_node_bracket(self.start_node)

    def ensure_bracket(self, child_bracket):
        if not child_bracket:
            return self.small_bracket
        child_bracket_order = self.brackets[child_bracket]
        for bracket, order in self.brackets.items():
            if order > child_bracket_order:
                return bracket
        return None

    def find_child_bracket(self, node):
        if not node:
            return
        bracket = node.data['origin'].get('bracket')
        if node.data['origin']['left'] != -1:
            left_bracket = self.find_child_bracket(self.formula_dict.get(node.data['origin']['left']))
            if left_bracket:
                if not bracket:
                    bracket = left_bracket
                else:
                    bracket = left_bracket if self.brackets[left_bracket] > self.brackets[bracket] else bracket
        if node.data['origin']['right'] != -1:
            right_bracket = self.find_child_bracket(self.formula_dict.get(node.data['origin']['right']))
            if right_bracket:
                if not bracket:
                    bracket = right_bracket
                else:
                    bracket = right_bracket if self.brackets[right_bracket] > self.brackets[bracket] else bracket
        return bracket

    def fill_node_bracket(self, start_node, level=1):
        start_node_priority = self.operator_priority.get(start_node.data['origin']['name'], self.priority_default)

        left = self.formula_dict.get(start_node.data['origin']['left'])
        if left:
            self.fill_node_bracket(left, level=level + 1)
            left_lowest_priority = self.get_lowest_priority(left)
            if left_lowest_priority < start_node_priority:
                child_bracket = self.find_child_bracket(left)
                left.data['origin']['bracket'] = self.ensure_bracket(child_bracket)

        right = self.formula_dict.get(start_node.data['origin']['right'])
        if right:
            self.fill_node_bracket(right, level=level + 1)
            right_lowest_priority = self.get_lowest_priority(right)
            if right_lowest_priority < start_node_priority or (start_node.data['origin']['name'] in ['/', '-'] and right_lowest_priority == start_node_priority):
                child_bracket = self.find_child_bracket(right)
                right.data['origin']['bracket'] = self.ensure_bracket(child_bracket)

    def get_lowest_priority(self, start_node):
        if not start_node or start_node.data['origin'].get('bracket'):
            return self.priority_default
        node_priority = self.operator_priority.get(start_node.data['origin']['name'], self.priority_default)
        if start_node.data['origin']['left'] != -1:
            left_priority = self.get_lowest_priority(self.formula_dict.get(start_node.data['origin']['left']))
            node_priority = min(node_priority, left_priority)
        if start_node.data['origin']['right'] != -1:
            right_priority = self.get_lowest_priority(self.formula_dict.get(start_node.data['origin']['right']))
            node_priority = min(node_priority, right_priority)
        return node_priority