2
\$\begingroup\$

I have been attempting to write a code that converts Prefix expressions to Postfix expressions.

So far here's what I have made (note that I am new and hence it may not be efficient!)

/***************************************************
 NOTE: This code fails to realise the precedence
    of parentheses and $ (exponential) expressions
****************************************************/

import java.util.Scanner;

class Stack{
    //Private Declarations
    private int top;
    private String a[] = new String [100];
    //Public Declarations
    public Stack(){
        top = -1;
        a[0] = "\0";
    }
    public void push(String x){
        if (top != 99){
            a[++top] = x;
        }
        else{
            System.out.println("Stack overflow");
        }
    };
    public String pop(){
        if (top == -1){
            System.out.println("\nStack empty!");
            return "\n";
        }
        else{
            return a[top--];
        }
    };
    public int ret_top(){
        return top;
    };
}


public class Prefix2Postfix {
    public static void main(String[] args) {
        //Declaration
        Scanner in = new Scanner (System.in);
        Stack op = new Stack ();
        Stack sym = new Stack ();
        char ch;
        int i;
        String exp, str, str1, str2, str3;

        //Taking input from the user
        System.out.println("Enter the prefix expression : ");
        exp = in.next();

        for (i=0; i<exp.length(); i++){
            ch = exp.charAt(i);
            if((ch == '+')
             ||(ch == '-')
             ||(ch == '*')
             ||(ch == '/')
             ||(ch == '$')){
                str = Character.toString(ch);
                op.push(str);
            }
            else{
                str = Character.toString(ch);
                sym.push(str);
            if (sym.ret_top() == 1){
                str1 = sym.pop();
                str2 = sym.pop();
                str3 = op.pop();
                str1 = str2.concat(str1);
                str1 = str1.concat(str3);
                sym.push(str1);
            }
            }
        }

        //Output
        str = sym.pop();
        System.out.println("After conversion to postfix" + ": " + str);
        in.close();
    }
}

As I have already commented in the code, my code fails to realize the precedence in the case of prefix expressions.

For example:

Infix : a + (b*c)

Prefix : +a*bc

Postfix : abc*+ //Expected output

Output I get : ab*c+

Is something wrong with the logic I am using, or is there something I need to add? Can you please suggest some method by means of which my code can work properly? If anybody can help I will be grateful.

NB: Our professor has advised us to write our own stack class and code. Please also note that this is kind of a homework assignment.

Edit: To make sure my Stack class works fine I have written this piece of code:

import java.util.Scanner;

class STACK {
    //Private Declarations
    private int top;
    private int elem[] = new int [100];
    //Public Declarations
    public STACK (){
        top = -1;
        elem[0] = 0;
    }
    public void push(int x){
        if (top != 99){
            elem[++top] = x;
        }
        else{
            System.out.println("Stack overflow");
        }
    };
    public int pop(){
        if (top == -1){
            System.out.println("Stack empty!");
            return 0;
        }
        else{
            return elem[top--];
        }
    };
}

public class StackPushPop {
    public static void main(String[] args) {
        STACK s = new STACK();
        Scanner in = new Scanner (System.in);
        int choice, x;
        do{
            System.out.println("Menu Options :");
            System.out.println("1 -> Push an element");
            System.out.println("2 -> Pop an element");
            System.out.println("3 -> Empty complete stack");
            System.out.println("Any other input for exit");
            System.out.println("Your choice : ");
            choice = in.nextInt();
            switch(choice){
                case 1: 
                    System.out.println("\nEnter element : ");
                    x = in.nextInt();
                    s.push(x);
                    break;
                case 2:
                    System.out.print("\nPopping element : ");
                    x = s.pop();
                    if (x != 0){
                        System.out.println(x);
                    }
                    break;
                case 3:
                    System.out.println("\nEmptying stack!");
                    x = 1;
                    while (x!= 0){
                        x = s.pop();
                        if(x != 0){
                            System.out.print(x + "  ");
                        }
                    }
                    break;
                default:
                    choice = 0;
            }

        }while (choice != 0);
    }
}
\$\endgroup\$

closed as off-topic by Aseem Bansal, Jamal, palacsint, Lstor, Nikita B Aug 30 '13 at 8:23

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions must contain working code for us to review it here. For questions regarding specific problems encountered while coding, try Stack Overflow. After your code is working you can edit this question for reviewing your working code." – Aseem Bansal, Jamal, palacsint, Lstor, Nikita B
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ May be here is bug: a[++top] = x; You will write first value at index 1, not 0. \$\endgroup\$ – k06a Aug 29 '13 at 11:05
  • \$\begingroup\$ @k06a : Please check the code properly. In my constructor I have assigned top to -1. Hence a[++top] = x; will first increase top to 0 and then store value at a[0]. \$\endgroup\$ – iluvthee07 Aug 29 '13 at 11:13
  • \$\begingroup\$ This is Java code. Why is there a C++ tag? \$\endgroup\$ – idoby Aug 29 '13 at 12:02
  • \$\begingroup\$ I am so sorry. I must have put it there by mistake. Thanks for pointing that out, I will remove it right away. \$\endgroup\$ – iluvthee07 Aug 29 '13 at 12:03
1
\$\begingroup\$

You should define a constant that represents the size of your array. If tomorrow you want the array to be 200 elements and just change

private String a[] = new String [200];

your code will break.

However if you class looked like the following, changing the size of the stack is simple and easy.

class Stack{
    private static final int STACK_SIZE = 100;
    private String a[] = new String [STACK_SIZE];
    //...
    public void push(String x){
        if (top <= STACK_SIZE-1){
            a[++top] = x;
        }
        else{
            System.out.println("Stack overflow");
        }
    };
}

Also, if you accidentally increment top by more than one, top != STACK_SIZE-1 can fail and cause an indexing error. Checking for less than or equal is what you want to do conceptually, so have the code actually do that.


public int ret_top(){
    return top;
};

The convention is to name this type of method getTop() (note both the name and casing).


You don't need to define all of you variables at the start of main(). Try to keep a variable as tightly scoped as you can. This will improve memory usage because instances you no longer need can be garbage collected. But more importantly, it will prevent you from accidentally using a value from a previous usage that you did not intend to use.

Additionally, names like str2 are not good variable names. The type system tells me that the variable is a String, so you shouldn't need to put the type in the name. Your variable names should describe what the value is conceptually. What makes a value popped from op different from a value popped from sym?

On more thing, you don't need to keep variable names to less than 5 characters. I can guess what sym and op stand for, but it would be better if the code just told me. You shouldn't jump to 50 character names, but actual words are generally better than abbreviations.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot! I am a beginner and am learning to code. I find your answer really useful in the long run. But it still does not answer my question and hence I can't accept it. \$\endgroup\$ – iluvthee07 Aug 29 '13 at 14:03
  • \$\begingroup\$ @iluvthee07: Code Review is designed for getting comments on code quality. Think "Is this code good? Could it be better?" For "Why doesn't this work?" StackOverflow is best. \$\endgroup\$ – unholysampler Aug 29 '13 at 15:22
  • \$\begingroup\$ I accept the point you brought to my notice. Thanks a lot! \$\endgroup\$ – iluvthee07 Aug 29 '13 at 15:50
0
\$\begingroup\$

You are talking about Polish notation (PN) and reverse Polish notation (RPN):

Looks like you need to write some tests for your stack and function to make sure all works fine.

And IMHO it will be more clear to rewrite your if with switch:

switch (ch)
{
    case '+':
    case '-':
    case '*':
    case '/':
    case '$':
         // ...

    default:
         // ...
}
\$\endgroup\$
  • \$\begingroup\$ My stack works fine but the fact that precedence in my Polish notation is ignored is whats bugging me. \$\endgroup\$ – iluvthee07 Aug 29 '13 at 10:54
  • \$\begingroup\$ @iluvthee07 only tests can prove yourcode works fine. Your comments can't :) \$\endgroup\$ – k06a Aug 29 '13 at 10:58
  • \$\begingroup\$ @iluvthee07 please post test, witch your code fails .. \$\endgroup\$ – k06a Aug 29 '13 at 11:01
  • \$\begingroup\$ I have given the test for which my code fails in the question, please see it. \$\endgroup\$ – iluvthee07 Aug 29 '13 at 11:03
  • 1
    \$\begingroup\$ @iluvthee07: JUnit is a popular unit test framework. Tutorial on JUnit Even if you don't end up using JUnit, the core concepts should carry over. \$\endgroup\$ – unholysampler Aug 29 '13 at 16:41

Not the answer you're looking for? Browse other questions tagged or ask your own question.