c# - 使用二叉树将中缀转换为后缀

Question

我正在尝试为后缀转换器制作一个中缀。我已经在 Google 中搜索过代码，但大多数算法都使用堆栈或使用大量正则表达式或难以理解，但我想用二叉树实现这一点。

这是我已经做过的:

类节点:

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 方法(我也写过 search、deletemin 等，但我的问题不需要它们)

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/

Answer 1

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