c# - Convert Infix to Postfix with Binary Tree -
i'm trying make infix postfix converter. have searched code in google of algorithms stack or using lot's of regular expression or hard understand, want make binary tree.
here have 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 using get/set instead of simple auto property.
and bst class has insert, postfix, prefix , infix method (i have writen search, deletemin, etc don't need them 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 work numbers example:
if want write inorder, preorder , 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 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 want make infix postfix converter don't know how implement insert method that, , how handle operator , operands in order. , problem parentheses.
grateful if me code.
an example tree:
mathblog has infix postfix converter, can check yours it.
http://www.mathblog.dk/tools/infix-postfix-converter/
it looks easiest way convert expression infix postfix notation use standard stack based algorithm(it has linear time complexity, optimal) , build tree(constructing tree postfix expression simple because operators in correct order).
Comments
Post a Comment