CODEWITHSUNDEEP
javastringstackpostfix-mta
user8076955
user8076955

Reputation:

Evaluate the value of an arithmetic expression in Reverse Polish Notation

we are given with String array, containing postfix expression as its elements and we need to do the evaluation

i tried this using stack but facing exception : Exception in thread "main" java.util.EmptyStackException

public int evalRPN(String[] A) {

     Stack<Integer> s=new Stack<>();
     int i=0;
     while(s.isEmpty()==false && i<A.length)
     {
        String p=A[i++];
        if(p.matches("\\d"))
            s.push(Integer.parseInt(p));
        else
            {
                int a=s.pop();
                int b=s.pop();

                switch(p)
                {
                    case "+": s.push(b+a);break;
                    case "-": s.push(b-a);break;
                    case "*": s.push(b*a);break;
                    case "/": s.push(b/a);break;


                }
            }

    }
    return s.pop();
 }

Upvotes: 0

Views: 863

Answers (2)

Jim Mischel
Jim Mischel

Reputation: 134055

There are several problems in your code. I've added comments to describe them.

public int evalRPN(String[] A) {

     Stack<Integer> s=new Stack<>();
     int i=0;

     // The stack will be empty on entry, so this loop is never executed.
     // You should change this to while (i < A.length)
     while(s.isEmpty()==false && i<A.length)
     {
        String p=A[i++];

        // This only matches a single digit. So something like "1X" would be
        // accepted. That will cause an error in the call to parseInt().
        // If you care about detecting invalid input, you'll have to handle
        // the exception, or find another way to do this.
        if(p.matches("\\d"))
            s.push(Integer.parseInt(p));
        else
            {
                int a=s.pop();
                int b=s.pop();

                switch(p)
                {
                    case "+": s.push(b+a);break;
                    case "-": s.push(b-a);break;
                    case "*": s.push(b*a);break;
                    case "/": s.push(b/a);break;
                    // You have no default case here, so the program will
                    // just ignore anything that is not, '+','-','*','/'
                }
            }

    }

    // Here, you should verify that s contains just one value. If s is empty,
    // or if s has 2 or more values, then the input was not a valid postfix
    // expression.
    return s.pop();
 }

Upvotes: 2

Islingre
Islingre

Reputation: 2349

public int evalRPN(String[] A) {

     Stack<Integer> s=new Stack<>();
     int i=0;
     while(i<A.length) //stack will be empty right at the start.. no need to check this
     {
        String p=A[i++];
        if(p.matches("\\d")) //I am not quite sure, but this just matches single digits, right? I would go for "\\d*", but I am not completely sure. Anyways you won't capture negative values or decimals.. perhaps better exclude +-*/ and use Double.parseDouble and a Stack<Double>
            s.push(Integer.parseInt(p));
        else
            {
                int a=s.pop();
                int b=s.pop();

                switch(p)
                {
                    case "+": s.push(b+a);break;
                    case "-": s.push(b-a);break;
                    case "*": s.push(b*a);break;
                    case "/": s.push(b/a);break;


                }
            }

    }
    return s.pop();
 }

This might run into an error if the given expression is not correct (too many operators / too few operands) or it might return just an intermediate result (too many operands / too few operators).

Upvotes: 2

Related Questions