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

[Anonymous]

Я пытаюсь создать преобразователь инфикса в постфикс. Я уже искал код в 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 вместо простого свойства auto.

и мой класс 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());
}
}
}

Мой метод вставки работает, например, для чисел:

Если мы хотим написать Inorder, Preorder и Post Order для дерева ниже



Предзаказ: 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/

Подробнее здесь: https://stackoverflow.com/questions/270 ... inary-tree