一阶谓词表达式转二叉树 Python

一阶谓词表达式转二叉树 Python 一阶谓词表达式转二叉树 Python

原理类似于中缀表达式转二叉树，把运算符的优先级换掉就可以了

但是谓词表达式要注意三个运算符﹁，∃x，∀x，因为它们三都是只有一个运算数的，需要单独处理

主要思想：输入中缀一阶谓词表达式，先将中缀表达式转后缀表达式，再将后缀表达式构建二叉树，最后打印二叉树

放上代码，有兴趣的同学可以看一下，还不太完善，有什么好的改进方法欢迎交流
可以加一个字符串的切分函数，以及错误判断

#####一阶谓词表达式转二叉树######
# coding:UTF8
import sys

from binarytree import build
import random
import networkx as nx
import matplotlib.pyplot as plt
from collections import defaultdict

from notebook.notebookapp import raw_input


class TNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    # 判断是否是运算符
    def isOper(self, ch):
        '''if ch in ['+', '-', '*', '/', '^', '(', ')']:
            return True
        return False'''
        if ch in ['!', '%x', '&x', '<', '>', '->', '(', ')', '%y', '&y']:
            return True
        return False

    # 获取运算符所对应的优先级别
    def getOperOrder(self, ch):
        if ch == '(':
            return 1
        if ch in ['!', '%x', '&x', '%y', '&y']:
            return 2
        if ch in ['<', '>']:
            return 3
        if ch == ['->','<->']:
            return 4
        if ch == '^':
            return 5
        return 0

    # 创建二叉树
    def createTree(self, data):
        if not data:
            return
        ch = data.pop(0)
        if ch == '#':
            return None
        else:
            root = TNode(ch)
            root.left = self.createTree(data)
            root.right = self.createTree(data)
            return root

    # 后缀表达式生成二叉树
    def PostExpTree(self, data):
        if not data:
            return
        re = []
        while data:
            tmp = data.pop(0)
            if not self.isOper(tmp):
                re.append(TNode(tmp))
            elif tmp in ['!', '%x', '&x', '%y', '&y']:   ##单独处理只有一个运算数的运算符
                p = TNode(tmp)
                p.right = re.pop()
                re.append(p)
            else:
                p = TNode(tmp)
                p.right = re.pop()
                p.left = re.pop()
                re.append(p)
        return re.pop()
        
# 中缀表达式生成二叉树
    def InExpTree(self, data):
        re = []
        op = []
        while data:
            tmp = data.pop(0)
            if not self.isOper(tmp):  #判断是否是运算符
                re.append(tmp)
            else:
                if tmp == '(':
                    op.append('(')
                elif tmp == ')':
                    while op[-1] != '(':
                        re.append(op.pop())
                    op.pop()
                elif tmp in ['!', '%x', '&x', '<', '>', '->','<->', '%y', '&y']:
                    while op and op[-1] != '(' and self.getOperOrder(op[-1]) > self.getOperOrder(tmp):
                        re.append(op.pop())
                    op.append(tmp)
        if op:
            re = re + op[::-1]
        #print(re)
        return self.PostExpTree(re)  #后缀表达式生成二叉树

def draw(node):  # 以某个节点为根画图
    saw = defaultdict(int)

    def create_graph(G, node, p_name, pos={}, x=0, y=0, layer=1):
        if not node:
            return
        name = str(node.val )
        saw[name] += 1
        if name in saw.keys():
            name += ' ' * saw[name]

        if layer != 1:
           G.add_edge(p_name, name)
        pos[name] = (x, y)

        l_x, l_y = x - 2 / 3 ** layer, y - 1
        l_layer = layer + 1
        create_graph(G, node.left, name, x=l_x, y=l_y, pos=pos, layer=l_layer)

        r_x, r_y = x + 2 / 3 ** layer, y - 1
        r_layer = layer + 1
        create_graph(G, node.right, name, x=r_x, y=r_y, pos=pos, layer=r_layer)
        return (G, pos)

    graph = nx.DiGraph()
    graph, pos = create_graph(graph, node, "     ")
    pos["     "] = (0, 0)
    fig, ax = plt.subplots(figsize=(8, 10))  # 比例可以根据树的深度适当调节
    nx.draw_networkx(graph, pos, ax=ax, node_size=1000)
    plt.show()


#data = ['&x', '(', 'd', '->', 'a', ')']
data = ['&x', '(', 'd', '->', '!', 'a', ')']
#data = ['(', '(', 'd', '->', 'a', ')', '->', 'c', ')']
#data = sys.stdin.readline().strip()
data = raw_input("input:")
data = data.strip().split()   #将输入按空格分隔，放入list中 
#print(type(data))
#print(data)
s = Solution()
res = []
#s.InorderTree(t1)
tree = s.InExpTree(data)  # 中缀表达式生成二叉树
s.InorderTree(tree)
res = map(str, res)
print(''.join(res))
draw(tree)

输出结果：