使用二叉树将中缀表达式转换为后缀表达式

Question

我正在尝试制作一个中缀表达式转后缀表达式的程序。我已经在Google上搜索了一些代码，但大多数算法都是使用堆栈或者使用许多正则表达式或难以理解的，但我想用二叉树来实现。

以下是我已经完成的内容：

类Node:

public class Node
{
    private object element;
    private Node left;
    private Node right;
    private Node parent;

    public Node()
    {
    }

    public Node(object x, Node r, Node l)
    {
        element = x;
        right = r;
        left = l;
    }

    public object GetElement()
    {
        return element;
    }

    public void SetElement(object x)
    {
        element = x;
    }

    public Node GetLeft()
    {
        return left;
    }

    public void SetLeft(Node l)
    {
        left = l;
    }

    public Node GetRight()
    {
        return right;
    }

    public void SetRight(Node r)
    {
        right = r;
    }

    public Node GetParent()
    {
        return parent;
    }

    public void SetParent(Node p)
    {
        parent = p;
    }
}

抱歉，我使用了get/set而不是简单的自动属性。

还有我的BST类，它有插入（Insert）、后序（Postfix）、前序（Prefix）和中序（Infix）方法（我还编写了搜索、删除最小值等方法，但我们不需要它们来回答我的问题）。

BST类：

public class BinarySearchTree
{
    //Node r: root.
    public void Insert(Node r, Node p, object x)
    {
        if (r == null)
        {
            r = new Node(x, null, null);
            r.SetParent(p);
            if ((int)x < (int)p.GetElement())
                p.SetLeft(r);
            else if ((int)x > (int)p.GetElement())
                p.SetRight(r);
        }
        if ((int) x < (int) r.GetElement())
            Insert(r.GetLeft(), r, x);
        else if ((int) x > (int) r.GetElement())
            Insert(r.GetRight(), r, x);
    }

    public void PreOrder(Node p)
    {
        if (p != null)
        {
            Console.WriteLine(p.GetElement());
            PreOrder(p.GetLeft());
            PreOrder(p.GetRight());
        }
    }

    public void Inorder(Node p)
    {
        if (p != null)
        {
            Inorder(p.GetLeft());
            Console.WriteLine(p.GetElement());
            Inorder(p.GetRight());
        }
    }

    public void Postorder(Node p)
    {
        if (p != null)
        {
            Postorder(p.GetLeft());
            Postorder(p.GetRight());
            Console.WriteLine(p.GetElement());
        }
    }
}

我的插入方法适用于数字，例如：
如果我们想要编写以下树的中序遍历、先序遍历和后序遍历

前序遍历：5、3、2、4、7、6、12
后序遍历：2、4、3、6、12、7、5
中序遍历：2、3、4、5、6、7、12

此示例的主要方法：

private static void Main()
{
    BinarySearchTree bst = new BinarySearchTree();
    Node r = new Node(5, null, null);
    bst.Insert(r, null, 3);
    bst.Insert(r, null, 7);
    bst.Insert(r, null, 4);
    bst.Insert(r, null, 12);
    bst.Insert(r, null, 2);
    bst.Insert(r, null, 6);
    bst.Inorder(r);
    Console.WriteLine();
    bst.Postorder(r);
    Console.WriteLine();
    bst.PreOrder(r);
}

现在我想制作一个中缀转后缀的转换器，但不知道如何实现插入方法，并如何按顺序处理运算符和操作数。另一个问题是括号。
如果您能提供一些代码帮助我，我将非常感激。

使用树的示例：

mathblog有一个中缀表达式转后缀表达式的转换器，您可以使用它来检查您的表达式。
http://www.mathblog.dk/tools/infix-postfix-converter/

- knight

---

你为什么想要用二叉搜索树来做呢？基于栈的算法既简单又高效。 - kraskevich

这是我的老师布置给我们的作业，要求我们使用二叉搜索树进行操作。我对如何插入树感到困惑，但这是一个很好的算法提高挑战。 - knight

你需要一棵二叉树，而不是一棵二叉搜索树。在二叉搜索树中，节点按值排序。在表达式的二叉树表示中，内部节点是运算符，叶节点是操作数（例如，在你的情况下是数字）。请参阅二叉表达式树以获取详细说明，包括如何创建它们的良好示例。 - Jim Mischel

@JimMischel，您链接中的示例是将后缀表达式转换为中缀表达式，但我想将中缀表达式转换为后缀表达式。您能否至少编写一些代码，仅限于* +。如果我理解了它，我会将其扩展。 - knight

@JimMischel我编辑了我的问题。（将BST更改为二叉树。） - knight

Answer 1

看起来将表达式从中缀转换为后缀表示法的最简单方法是使用标准的基于堆栈的算法（它具有线性时间复杂度，因此是最优的），然后构建一棵树（从后缀表达式构建树很简单，因为所有运算符都按正确顺序排列）。

- kraskevich

---

@masoodm 你可以在栈上维护子表达式的根，然后在应用操作时将它们组合成一个新的根。最终，你在栈上只会有一个树节点：整个树的根。 - kraskevich