Convert Infix to Postfix with Binary Tree

Question

I'm trying to make an infix to postfix converter. I have already searched for code in Google but most of the algorithms were with stack or using lot's of regular expression or hard to understand, but I want to make this with Binary Tree.

here is what i have already did:

Class 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;
    }
}

Sorry for using get/set instead of simple auto property.

and my BST class that has Insert, Postfix, Prefix and Infix method (i have also writen search, deletemin, etc but we don't need them for my question)

BST Class:

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

My insert method is work for numbers for example:
If we want to write Inorder, Preorder and post order of below tree

Preorder: 5, 3, 2, 4, 7, 6, 12
Postorder: 2, 4, 3, 6, 12, 7, 5
Inorder: 2, 3, 4, 5, 6, 7, 12

Main method for this example:

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);
}

now I want to make a infix to postfix converter but don't know how to implement insert method for that, and how to handle operator and operands in order. and another problem is parentheses.
would be grateful if help me with some code.

An example with tree:

mathblog has a infix to postfix converter, you can check yours with it.
http://www.mathblog.dk/tools/infix-postfix-converter/

Answer 1

It looks like the easiest way to convert the expression from infix to postfix notation is to use a standard stack based algorithm(it has linear time complexity, so it is optimal) and then to build a tree(constructing a tree from postfix expression is simple because all operators are in a correct order).