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
{
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
http://i.stack.imgur.com/8zvhs.jpg[
^]
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 make insert method for that, i mean how to handle operator and operands in order. and another problem is how to handle parentheses. would be grateful if help me with some code.
an example with tree:
http://i.stack.imgur.com/1lk3U.jpg[
^]
mathblog has a infix to postfix converter, you can check yours with it.
http://www.mathblog.dk/tools/infix-postfix-converter/
I have asked this question before on stackoverflow but didn't get any answer.