Hi,I hope someone will help me on this,does anyone here knows algorithm BST infix to postfix,can you help me please.
I am not good in java and i am still getting know with this.
Thank you in advance.
toring
0
Light Poster
Recommended Answers
Jump to PostI don't know. I never studied computer science. But ata guess - no, it's not possible not to use a stack.
Jump to PostIt's not hard to test each char to see if it's a numeric or an operator
Jump to PostIn the case of
5*4/9I would make a BST that looks like:"*" / \ "5" "/" / \ "4" "9"
Jump to Postuh, you have to learn to think for yourself at some point...
All 46 Replies
JamesCherrill
4,733
Most Valuable Poster
Team Colleague
Featured Poster
Yes, many people here have done projects in that area.
Hoever, DaniWeb Member Rules (which you agreed to when you signed up) include:
"Do provide evidence of having done some work yourself if posting questions from school or work assignments"
http://www.daniweb.com/community/rules
Post what you have done so far and someone will help you from there.
toring
0
Light Poster
Hi JamesCherill,..Thank you for the reply...This where i get stuck.,I have no idea yet how can i achieve BST infix to postfix,..I hope you can help me on this...I just want to know the algorithm so that i can have idea,.I am still newbie on java programming. Thank you in advance
public class BSTNode{
private int item;
private BSTNode left;
private BSTNode right;
public BSTNode (){}
public BSTNode (int item){
this.item = item;
}
public BSTNode(int item){
this(item);
}
public void setRight(int item) {
BSTNode temp = new BSTNode(item);
this.right = temp;
}
public void setLeft(int item) {
BSTNode temp = new BSTNode(item);
this.left = temp;
}
public void setItem(int item){
this.item = item;
}
public int getItem() {
return item;
}
public BSTNode getLeft() {
return left;
}
public BSTNode getRight() {
return right;
}
public boolean isEmpty()
{
return root==null;
}
public void infix(int n){
//here i am stuck,...
}
public static void main(String [] args){
BSTNode root = new BSTNode(50);
}
}
JamesCherrill
4,733
Most Valuable Poster
Team Colleague
Featured Poster
You could start with Google. There are many sites with tutorials on the theory and implementation. You can't expect someone here to write a new one just for you!
toring
0
Light Poster
Hi James,I understand i did not expect someone to write for me a code,i just want to know a little idea so that i can start writing my code...
JamesCherrill
4,733
Most Valuable Poster
Team Colleague
Featured Poster
I just googled
algorithm BST infix to postfix
and immediately got a whole load of tutorials and samples.
Start with those and come back here if you get stuck
toring
0
Light Poster
Hi James, Maybe i am in the wrong forum to ask some help,,this is not for the beginners or beginners are not get much more help here, this is for an advance people like you...I think!
Slavi
94
Master Poster
Featured Poster
You are on the right place its just you expect the entire algorithm given at once, if you really want to learn how to do it, start by what you did and ask a specific question about the code where you are stucked, or why does your code not work/what kind of errors you get.
JamesCherrill
4,733
Most Valuable Poster
Team Colleague
Featured Poster
Maybe 90% of the people who get help here are beginners. But we do expect people to show some initiative and put in some work if they expect us to take time with them.
toring
0
Light Poster
Hi,James can you please give me the links,
JamesCherrill
4,733
Most Valuable Poster
Team Colleague
Featured Poster
toring
0
Light Poster
Thanks, I'll be back.
toring
0
Light Poster
Hi James,
How do i print the data that i inserted ?..
public class BSTO {
BSTO rightchild;
BSTO leftchild;
int data;
BSTO root;
public BSTO(){}
public void Insert(int data){
BSTO newnode = new BSTO();
newnode.data = data;
newnode.leftchild = null;
newnode.rightchild = null;
BSTO current = null;
BSTO temp = null;
if(root==null){
root = newnode;
}else{
temp = root;
while(temp!=null){
current = temp;
if(data<current.data)
{
temp=temp.leftchild;
if(temp==null){
current.leftchild = newnode;
return;
}
}
else
{
temp=temp.rightchild;
if(temp==null){
current.rightchild = newnode;
return;
}
}
}//End while
}
}
public static void main(String []args){
BSTO bsto = new BSTO();
bsto.Insert(5);
bsto.Insert(8);
bsto.Insert(4);
bsto.Insert(6);
bsto.Insert(2);
bsto.Insert(3);
bsto.Insert(9);
}
}
JamesCherrill
4,733
Most Valuable Poster
Team Colleague
Featured Poster
You'll need to traverse the whole tree by following the leftchild and rightchild links. That requires a recursive solution - a quick Google for
BST traversal recursive
will give you a load of useful references.
toring
0
Light Poster
Hi james,Is this correct?
public class BSTO {
BSTO rightchild;
BSTO leftchild;
Character data;
BSTO root;
public BSTO(){}
public void Insert(Character data){
BSTO newnode = new BSTO();
newnode.data = data;
newnode.leftchild = null;
newnode.rightchild = null;
BSTO current = null;
BSTO temp = null;
if(root==null){
root = newnode;
}else{
temp = root;
while(temp!=null){
current = temp;
if(data<current.data)
{
temp=temp.leftchild;
if(temp==null){
current.leftchild = newnode;
return;
}
}
else
{
temp=temp.rightchild;
if(temp==null){
current.rightchild = newnode;
return;
}
}
}//End while
}
}
private void postOrder(BSTO rot)
{
if(rot != null)
{
postOrder(rot.leftchild);
postOrder(rot.rightchild);
System.out.print(rot.data + " ");
}
}
public static void main(String []args){
BSTO bsto = new BSTO();
bsto.Insert('5');
bsto.Insert('*');
bsto.Insert('2');
bsto.Insert('/');
bsto.Insert('6');
bsto.postOrder(bsto.root);
}
}
JamesCherrill
4,733
Most Valuable Poster
Team Colleague
Featured Poster
Right general area, yes. Time to try it out!
toring
0
Light Poster
Hi james, Okay it prints now but is there something that i will do to output postfix?..by the way is that correct I use Character not char ?
JamesCherrill
4,733
Most Valuable Poster
Team Colleague
Featured Poster
"is there something that i will do to output postfix?" Google is your friend.
"is that correct I use Character not char?" In this case I can't see any reason for chosing one or the other. In any case, Java will automatically convert between them ("boxing" and "unboxing") as needed. So don't worry.
toring
0
Light Poster
Hi james, I really could not find how to do it infix to postfix in BST
JamesCherrill
4,733
Most Valuable Poster
Team Colleague
Featured Poster
toring
0
Light Poster
Hi james,Is it possible not to use stack?
JamesCherrill
4,733
Most Valuable Poster
Team Colleague
Featured Poster
I don't know. I never studied computer science. But ata guess - no, it's not possible not to use a stack.
Hiroshe
499
Posting Whiz in Training
Hi james,Is it possible not to use stack?
What do you mean by that? The system stack or your own stack? You can convert infix to postfix using a lot of things. You should be able to write it using a BST without using your own stack if you wanted:
Step 1: Parse infix into BST recursively.
Step 2: Write BST in postfix notation.
You could also use your own stack to traverse the BST iteratively. You could also just use your own stack to do it iteratively. You could also just do it recursively without any extra data structure.
In all cases though, your either using the system stack or your own stack.
toring
0
Light Poster
I am asking because i am confuse if we use the stack to produce postfix then the result of postfix is on the stack not on the tree...
toring
0
Light Poster
Hi james,Do i need to create another method to convert the infix to postfix?..I am confuse on this..I thought postorder will give us the postfix result.
toring
0
Light Poster
Hi james why is it 20 will read only 2?
public class BSTO {
BSTO rightchild;
BSTO leftchild;
char data,ndata;
BSTO root;
public BSTO(){}
public void Insert(String n){
BSTO newnode = new BSTO();
char [] cc;
cc = n.toCharArray();
newnode.data = cc[0];
newnode.leftchild = null;
newnode.rightchild = null;
BSTO current = null;
BSTO temp = null;
if (root == null) {
root = newnode;
} else {
temp = root;
while (temp != null) {
current = temp;
if (ndata < current.data) {
temp = temp.leftchild;
if (temp == null) {
current.leftchild = newnode;
return;
}
} else {
temp = temp.rightchild;
if (temp == null) {
current.rightchild = newnode;
return;
}
}
}//End while
}
}
private void postOrder(BSTO rot)
{
if(rot != null)
{
postOrder(rot.leftchild);
postOrder(rot.rightchild);
System.out.print(rot.data + " ");
}
}
public static void main(String []args){
BSTO bsto = new BSTO();
bsto.Insert(new String("5"));
bsto.Insert(new String("*"));
bsto.Insert(new String("20"));
bsto.postOrder(bsto.root);
}
}
The output of postorder is: 2 * 5
JamesCherrill
4,733
Most Valuable Poster
Team Colleague
Featured Poster
Maybe because you store the data in a char, which only holds one character?
On lines 15-19 you carefully take just the first character from the String and ignore the rest.
toring
0
Light Poster
Okay i fixed it but the output is: 02*5
can i ask during the insert method do in need to convert it to postfix so that in my method postorder the output will be correct ?...
toring
0
Light Poster
This is the code but the output is : 0 2 * 5
public void Insert(String str){
for(int i=0;i<str.length();i++){
BSTO newnode = new BSTO();
cc = str.toCharArray();
newnode.data = cc[i];
newnode.leftchild = null;
newnode.rightchild = null;
if (root == null) {
root = newnode;
} else {
temp = root;
while (temp != null) {
current = temp;
if (cc[i] < current.data) {
temp = temp.leftchild;
if (temp == null) {
current.leftchild = newnode;
break;
}
} else {
temp = temp.rightchild;
if (temp == null) {
current.rightchild = newnode;
break;
}
}
}//End while
}
}//for loop
}
JamesCherrill
4,733
Most Valuable Poster
Team Colleague
Featured Poster
I have no idea why you are inserting your strings as multiple nodes, one per character... But that's why your "20" becomes "0" and "2"
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.