[Java] Accepted Code: Stack implementation.


  • 48
    P

    Hi everyone.
    The Reverse Polish Notation is a stack of operations, thus, I decided to use java.util.Stack to solve this problem. As you can see, I add every token as an integer in the stack, unless it's an operation. In that case, I pop two elements from the stack and then save the result back to it. After all operations are done through, the remaining element in the stack will be the result.
    Any comments or improvements are welcome.

    Cheers.

    import java.util.Stack;
    
    public class Solution {
        public int evalRPN(String[] tokens) {
            int a,b;
    		Stack<Integer> S = new Stack<Integer>();
    		for (String s : tokens) {
    			if(s.equals("+")) {
    				S.add(S.pop()+S.pop());
    			}
    			else if(s.equals("/")) {
    				b = S.pop();
    				a = S.pop();
    				S.add(a / b);
    			}
    			else if(s.equals("*")) {
    				S.add(S.pop() * S.pop());
    			}
    			else if(s.equals("-")) {
    				b = S.pop();
    				a = S.pop();
    				S.add(a - b);
    			}
    			else {
    				S.add(Integer.parseInt(s));
    			}
    		}	
    		return S.pop();
    	}
    }

  • 4
    Z

    althgouth it can be AC. but this implementation has issue that if test data is {"3","0","/"}; will cause a exception:

    Exception in thread "main" java.lang.ArithmeticException: / by zero


  • 0
    P

    Good observation. Thanks!


  • 0
    Y

    if{ "5" "-" }?


  • 0
    S

    Why not use S.push(), which I think is, maybe, safer and easy understanding, since it is in Stack class. What's the difference between add() and push()?


  • 0
    P

    push() is addElement(E e), add(E e) is an inherited method from Vector that uses List that will virtually have the same effect as push(). But I think you're right, push() makes the code more readable by clarifying that S is using a stack operation that will act in a certain way. Good observation.
    Thanks for your comment.


  • 0
    D

    What is AC? And isn't that an invalid / undefined input?


  • 0
    P

    I think he meant "Accepted" with AC. He is right, this code should check if the input provided can be actually computed. We can't always assume the input provided is correct and the computational time needed to add this verification is O(1) (constant time, really low).


  • 0
    D

    Agree that we can't assume the input provided is correct in general. However, for the purpose of the OJ, without guidance on what the value of inputs like n / 0 should be for any n, we have to assume that the input will be valid for the test cases that they provide.


  • 0
    H

    I used the Exception to control the operator flow, not sure this is a acceptable idea or not:
    public int evalRPN(String[] tokens) {
    Stack<Integer> numStack = new Stack<>();
    int result = 0;

       for (int i=0; i<tokens.length; i++) {
    
            try {
                int num = Integer.parseInt(tokens[i]);
                numStack.push(num);
            }
            catch (Exception e) {
                    int num2 = numStack.pop();
                    int num1 = numStack.pop();
                    switch (tokens[i]) {
                        case "/": result = num1/num2; 
                        case "-": result = num1 - num2; 
                        case "*": result = num1 * num2; 
                        default: result = num1 + num2; 
                    }
                    numStack.push(result);
    
            }
       }
       return numStack.pop();
        
    }
    

    }


  • 0
    S

    How can you push (a/b) onto the stack? Wouldn't this cause rounding problems?


  • 0
    D

    vote for b = S.pop();a = S.pop(); S.add(a / b); S.add(S.pop() * S.pop()); YOU ART GREAT


  • 0
    H

    @hans3 for this test case ["4", "13", "5", "1", "+", "/"], the result should be 2, but your code return 19.


  • 1
    A

    @hans3 you forgot to "break;" in each branch


  • 0

    Can anyone help with the situation when the input is invalid? eg. [ +, 10, /] I tried isNumetric() but it doesn't work. Thanks!


  • 0

    @hua.zhang20150913 based on my understanding of the rule, this case is maybe invalid. I am not sure how to make 4 involved in the calculation. Operators always deal with the closet two numbers on its left side.
    13 / (5+1), then there is no way for 4 to get involved in.


  • 0

    @Juan55555 I am sharing my way of implementation. Push only numbers to your stack. During your loop, when operators found, pop two numbers from the stack and do the calculation. In the case you post, when found "+", you can check if there is at least two numbers can be popped out from the stack, then do the calculation.


  • 0

    @pvaldes Could you explain how does your code handle the case "a / b" where b is zero? Thanks!


  • 0

    @zolibra I don't see this handle in some other solutions for this question either. What I found interesting for this code is that it actually gets accepted by LC...


  • 0
    public class Solution {
        public int evalRPN(String[] tokens) {
            Deque<Integer> stack = new ArrayDeque();
            for (String s : tokens) {
                if (s.charAt(s.length() - 1) >= '0' && s.charAt(s.length() - 1) <= '9') { // if it's number
                    stack.push(Integer.valueOf(s));
                } else { // +-*/
                    int cur = stack.pop(), pre = stack.pop();
                    stack.push(cal(pre, s.charAt(0), cur));
                }
            }
            return stack.pop();
        }
        
        private int cal(int a, char p, int b) {
            switch (p) {
                case '+': return a + b;
                case '-': return a - b;
                case '*': return a * b;
                case '/': return a / b;
            }
            return -1;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.