0

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.

0

@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.

0

@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+

0

@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.

0

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.

0

@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, +, -]

0

@Taywin,..I don't know if i correctly followed your alogrithm..i think there is missing in my code.Pleae guide me on this.

0

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.

Edited by Taywin

0

@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.

Edited by ezekel

0

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.

Edited by Taywin

0

@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.

0

@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 ?

0

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.

Edited by Taywin

0

@Taywin what should i put to else if? i am confuse.

0
@Taywin i am confuse about this else if,what do you mean by this...please help me on this.
0

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.

Edited by Taywin

0

@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));        
    }



}
0

@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/-

Edited by ezekel

0

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.
0

@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..?
         }


    }

Edited by ezekel

0

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.

0

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...

0

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. :)

0

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.?

0

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. ;)

0

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.

0

@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.

0

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

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.