Преобразование инфикса в постфикс с помощью двоичного дерева ⇐ C#

[Гость]

Я пытаюсь создать конвертер инфикса в постфикс. Я уже искал код в Google, но большинство алгоритмов были со стеком или множеством регулярных выражений, или их было трудно понять, но я хочу сделать это с помощью двоичного дерева.

< p>вот что я уже сделал:

Узел класса:

Код: Выделить всё

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/


Источник: https://stackoverflow.com/questions/270 ... inary-tree