I find it very useful when writing code for an algorithm to write a descrition of the steps I am coding as comments just before the code. That way when writing the code, I can look at the comments to see what the code is supposed to do.
NormR1 563 Posting Sage Team Colleague
ezekel 0 Junior Poster in Training
@Taywin @NormR1...did i followed the algorithm?..
System.out.print("Enter infix: ");
String str =new java.util.Scanner(System.in).next();
Infix=new Object[str.length()];
postfix=new Object[str.length()];
char [] cc = str.toCharArray();//convert to Array of character
for(int i=0;i < Infix.length;i++)
{
ch=cc[i];//Accept an array of character
if(Character.isDigit(ch)) //check if the input is a digit.
postfix[count++]=ch; //if it is digit append to output string.
else //it is '+','-','*','/'
{
if(!s.isEmpty())//check if the stack is not empty..
{
Character x = (Character)s.peek();//cast it to the actual type
while(!s.isEmpty())//stack is not empty
{
if(s.priority(x.charValue())<=s.priority(ch))//test if it is in greater than or equal priority
{
postfix[count++]=s.pop();//pop and append to the output string.
}
else
s.push(ch);//push it to the stack if it is less than...
}
}
else
s.push(ch);//stack is empty on the first time,push some element..
}
}
while(!s.isEmpty())
{
postfix[count++]=s.pop();
}
System.out.println("Postfix= " + Arrays.toString(postfix));//Displaying the value
here is the output...
Enter infix: 1+2+3
Postfix= [1, 2, +, 3, null]
Process completed.
ezekel 0 Junior Poster in Training
@Taywin,I am too close to the answer
char [] cc = str.toCharArray();
for(int i=0;i < Infix.length;i++)
{
ch=cc[i];
if(Character.isDigit(ch))
postfix[count++]=ch;
else
{
if(s.isEmpty())
s.push(ch);
else
{
Character x = (Character)s.peek();
while(!s.isEmpty())
{
if(s.priority(x.charValue())<=s.priority(ch))
{
postfix[count++]=s.pop();
}
else
break;
}
s.push(ch);
}
}
}
while(!s.isEmpty())
{
postfix[count++]=s.pop();
}
System.out.println("Postfix= " + Arrays.toString(postfix));
}
Here is the ouput
Enter infix: 1+5*6/5-8+9
Postfix= [1, 5, 6, *, +, 5, /, 8, -, 9, +]
The answer must be like this...
156*5/+8-9+
JamesCherrill 4,733 Most Valuable Poster Team Colleague Featured Poster
@JamesCherill @NormR1...May i excuse?...i just want to ask what is boxing and unboxing?Thank you.
Sorry for the delay in replying (nighttime here!). It's when the compiler sees you using a char when it should be a Character, or vice-versa. The compiler will "box" your char into a Character, or "unbox" the Character into char for you without you having to write any code. It was new in Java 1.5, and enhanced in 1.7 to include the cast situation that Norm & I were discussing.
Taywin 312 Posting Virtuoso
Maybe you could try to change if(s.priority(x.charValue())<=s.priority(ch)) to if(s.priority(x.charValue())<s.priority(ch)) and see what happen in the result.
ezekel 0 Junior Poster in Training
@Taywin.
Maybe you could try to change if(s.priority(x.charValue())<=s.priority(ch)) to if(s.priority(x.charValue())<s.priority(ch)) and see what happen in the result.
This is the output...
Enter infix: 1+5*6/5-8+9
Postfix= [1, 5, 6, 5, /, *, +, 8, 9, +, -]
ezekel 0 Junior Poster in Training
@Taywin,..I don't know if i correctly followed your alogrithm..i think there is missing in my code.Pleae guide me on this.
Taywin 312 Posting Virtuoso
In line 20, you need that x to be assigned inside your loop... If not, once the priority of the operator in the stack is higher than what you are currently pointing, it will keep popping the stack until it is empty.
Let me rewrite the algorithm to be even clearer... I think I omitted something that could lead to misunderstanding...
Define a stack (empty)
Go through each character in the string
If it is between 0 to 9, append it to output string.
Else If it is operator *+-/ then
If the stack is empty push it to the stack
Else (the stack is not empty)
While the stack is not empty
Peek the priority of the top item on the stack as X
If X has higher or equal priority than the operator
Then pop and append to output string
Else
Break
End IF
End While
Push the operator to the stack
End If
Else (invalid character)
Handle the invalid character (either ignore or throw an error)
End If
If there is any input in the stack pop and append to the output string.
In your current code, you assume that any other chars that are not digit would be an operator. You could try to enter a string with invalid chars to see what happen. It is up to you to deal with invalid chars in the input string.
ezekel 0 Junior Poster in Training
@Taywin,I think i spot now the missing...I hope this is correct now...yes i will trapp also invalid char after this will fixed...is my code correct now?
Character x = (Character)s.peek();
while(!s.isEmpty()&& x!=null)//test if x is not null...
{
if(s.priority(x.charValue())<=s.priority(ch))
{
postfix[count++]=s.pop();
x = (Character)s.peek();//this my missing...
}
else
break;
}
s.push(ch);
Enter infix: 12/5-6+3+21/8
Postfix= [1, 2, *, 5, /, 6, -, 3, +, 2, 1, *, 8, /, +]
Process completed.
Enter infix: 1+5*6/5-8+9
Postfix= [1, 5, 6, *, 5, /, +, 8, -, 9, +]
Process completed.
Taywin 312 Posting Virtuoso
Hmm... still looks odd to me... Could you change it to s.priority(x.charValue()>=priority(ch) instead?
To trap invalid character, you may need to change your "else" to "else if" instead; otherwise, all other chars besides digit will go into the "else" condition.
ezekel 0 Junior Poster in Training
@Taywin i tried also to put this
x = (Character)s.peek();
inside my while loop before the if statement as what your alogorithm says,and it comes up with the correct answer...my question is,is that also correct to put that inside in my if statement?if not so i will change same as yours algorithm.
ezekel 0 Junior Poster in Training
@Taywin if i am going to change to this my ouput will be wrong...
Hmm... still looks odd to me... Could you change it to s.priority(x.charValue()>=priority(ch) instead?
here is the sample...
Enter infix: 1+32-2+6-35+6*5-6/2
Postfix= [1, 3, +, 2, 2, -, 6, +, 3, -, *, 5, 6, +, *, 5, 6, -, *, 2, /]
Process completed.
Because in my method priority this is the structure...
public int priority(char c)
{
int p=999;
switch(c)
{
case '*':case '/': p=0; break;
case '+':case '-': p=1; break;
}
return p;
}
I thinks thats the reason why i get wrong output...
To trap invalid character, you may need to change your "else" to "else if" instead; otherwise, all other chars besides digit will go into the "else" condition.
what is my elseif ?
Taywin 312 Posting Virtuoso
I believe it is still corrected if you put the peek() in your if statement. The reason is that the value of peek() needs to be changed after the stack is popped. In the loop, if the stack is not popped, it will get out of the loop. Also, the peek() value will not be used again after the loop, so whatever happens inside the loop is unknown to the statement after the loop.
ezekel 0 Junior Poster in Training
@Taywin what should i put to else if? i am confuse.
ezekel 0 Junior Poster in Training
@Taywin i am confuse about this else if,what do you mean by this...please help me on this.
Taywin 312 Posting Virtuoso
According to the code in the 3rd post of this page (starts with char[] cc), Line 10 should be else if instead of else and add an else in line 38 (where the close curly bracket is). Whatever content in the new else will be whatever you want to handle with invalid characters.
ezekel 0 Junior Poster in Training
@Taywin is this what you mean?
import java.util.Arrays;
public class InfixToPostfix
{
Object[] stack;
int top;
int size;
public InfixToPostfix(){
}
public InfixToPostfix(int size)
{
stack=new Object[size];
top=0;
}
public boolean isEmpty()
{
return top==0;
}
public boolean isFull()
{
return top==stack.length;
}
public boolean push(Object item)
{
boolean ok=!isFull();
if(ok)
{
stack[top++]=item;
ok= true;
}
return ok;
}
public Object peek()
{
// return stack[top-1];
Object s =null;
if(!this.isEmpty())
s = stack[top-1];
return s;
}
public Object pop()
{
Object item=peek();
if(item!=null)
{
stack[top-1]=null;
top--;
}
return item;
}
public int priority(char c)
{
int p=999;
switch(c)
{
case '*':case '/': p=0; break;
case '+':case '-': p=1; break;
}
return p;
}
public static void main(String...args)
{
InfixToPostfix s =new InfixToPostfix(20);
Object[] Infix;
Object[] postfix;
int count=0;
char ch='\u0000';
System.out.print("Enter infix: ");
String str =new java.util.Scanner(System.in).next();
Infix=new Object[str.length()];
postfix=new Object[str.length()];
char [] cc = str.toCharArray();
for(int i=0;i < Infix.length;i++)
{
ch=cc[i];
if(Character.isDigit(ch))
postfix[count++]=ch;
else if(ch=='*' || ch=='/' || ch=='+' || ch=='-')
{
if(s.isEmpty())
s.push(ch);
else
{
Character x = (Character)s.peek();
while(!s.isEmpty())
{
x = (Character)s.peek();
if(s.priority(x.charValue())>=s.priority(ch)){
postfix[count++]=s.pop();
}
else
break;
}
s.push(ch);
}
}
else
{
System.out.print("Ivalid character");
}
}
while(!s.isEmpty())
{
postfix[count++]=s.pop();
}
System.out.println("Postfix= " + Arrays.toString(postfix));
}
}
Taywin 312 Posting Virtuoso
Correct.
ezekel 0 Junior Poster in Training
@Taywin,How do i handle this
2*6(5+4)-2/8
it has the open and close parenthesis.
the out put should be this.
2654+*28/-
Taywin 312 Posting Virtuoso
You need a little modification...
Define a stack (empty)
Go through each character in the string
If it is between 0 to 9, append it to output string.
Else If it is a left parenthesis
Push the symbol on the stack
Else If it is operator *+-/ then
If the stack is empty push it to the stack
Else (the stack is not empty)
While the stack is not empty
Peek the priority of the top item on the stack as X
If X has higher or equal priority than the operator
Then pop and append to output string
Else
Break
End IF
End While
Push the operator to the stack
End If
Else If it is a right parenthesis
While stack not empty and top not equal to left parenthesis
Pop the stack and append to output string
If the stack is empty
Handle the mismatch parenthesis
Else
Pop out the encountered left parenthesis
End If
Else (invalid character)
Handle the invalid character (either ignore or throw an error)
End If
If there is any input in the stack pop and append to the output string.
ezekel 0 Junior Poster in Training
@Taywin, I hope i did not missed something on your algo.
for(int i=0;i < Infix.length;i++)
{
ch=cc[i];
if(Character.isDigit(ch))
postfix[count++]=ch;
else if(ch=='*' || ch=='/' || ch=='+' || ch=='-')
{
if(s.isEmpty())
s.push(ch);
else
{
Character x = (Character)s.peek();
while(!s.isEmpty())
{
x = (Character)s.peek();
if(s.priority(x.charValue())<=s.priority(ch)){
postfix[count++]=s.pop();
}
else
break;
}
s.push(ch);
}
}
else if(ch=='(')
{
s.push(ch);
}
else if(ch==')')
{
Character cr = (Character)s.peek();
while(!s.isEmpty() && cr.charValue()!='(')
{
postfix[count++]=s.pop();
cr=(Character)s.peek();
}
if(s.isEmpty())
{
System.out.print("parenthesis mismatched");
System.exit(0);
}
s.pop();
}
else
{
System.out.print("Invalid");
System.exit(0);
}
}
while(!s.isEmpty())
{
postfix[count++]=s.pop();
}
System.out.print("Postfix= ");
for(int i=0;i<count;i++)
{
System.out.print(postfix[i]); // Is this will not cause memory leak..?
}
}
Taywin 312 Posting Virtuoso
Sorry for not replying for a couple of days. Looks fine to me. Have to tried to run it?
By the way, what do you mean by memory leak??? In Java, memory is being managed Java and will be clean up by Garbage Collector. You do nothing. If you are asking about whether the postfix variable data type is good for this application, I would say no. You could simply use a String type and append each character to it. Nevertheless, it is your choice and there is nothing really wrong with it.
ezekel 0 Junior Poster in Training
Have to tried to run it?
Yes i have tried it,and it works...I got the correct output...
If you are asking about whether the postfix variable data type is good for this application, I would say no.
why? can you please enligthen my mind...
Taywin 312 Posting Virtuoso
The reason is that your postfix data type is a fixed array of Object but being used as char. You will need to create it before you can use it. Also, you need one more variable to keep track of where item should be put into.
String class works exactly the same way but it is robust. Its memory management is already included in the class implementation (such as where to put the next item, etc.). Also, it makes this application easier. Because the application purpose is very narrow (accepts specific charaters), use of Object is overkill and more difficult to maintain for future use.
Though, as I said before, it is fine if you insist on using what you do because you could learn more. In practice, please do not use this because it will create problems in the future for either you or those who have to take over your work. :)
ezekel 0 Junior Poster in Training
You will need to create it before you can use it.
What do you mean to create it first before i can use it.
The reason is that your postfix data type is a fixed array of Object but being used as char.
But how can i declare the size of my postfix.?
Taywin 312 Posting Virtuoso
When you use a fixed array, you need to declare the limitation of it first as Object[] postfix = new Object[length];. For a String, you could simply use String postfix = "";. Because appending string needs no knowledge of how long the string would be, you do not need to know what size in order to append it. The array object, on the other hand, needs an index which must be in the range of whatever it is created. The index is another variable that the program keeps in the memory in order to keep track of the array while working through. Anyway, it does not matter what you choose for learning purpose. You will find out more when you work anyway. ;)
JamesCherrill 4,733 Most Valuable Poster Team Colleague Featured Poster
This could be miseading. Strings in Java are immutable, you can never change or add to them. "appending to a String" is actually creating a new String with the contents of the old string plus the appended char(s), so it's a horribly inefficient way to process any real quantity of appends.
If you want to append to a string repeatedly, use a StringBuilder rather then a String. StringBuilders are mutable and were designed for that purpose.
ezekel 0 Junior Poster in Training
@JamesCherrill,
Can you please show me some snippet of code of what do you mean.Because i am confuse.or please put some correction on my codes.so that i can see where i am wrong.I hope you grant me.
Taywin 312 Posting Virtuoso
Ah yes, I should have mentioned that. Thanks James. :)
JamesCherrill 4,733 Most Valuable Poster Team Colleague Featured Poster
Hi ezekal
Don't worry. I was not saying your code was wrong. Taywin's post was possibly confusing for some readers so I tried to set it right. Just concentrate on getting your program to work for now.
J
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.