150. Evaluate Reverse Polish Notation - Medium

前往題目

之前寫過，搬運一下

想法

• 這題應該算是easy才對，五分鐘就想出來了，但也有可能是因為有先備知識
• 這題的先備知識就是Stack，不熟練以及不熟悉Stack的特性有可能會想不出來
• 少數自己想出來的medium，開心😆

思路

1. 建立stack
2. 疊代所有token
3. 遇到symbol就pop兩個數字然後做運算
4. 結果push回stack裡
5. 直到token都用完
6. 回傳stack.pop，因為這時stack只會剩下一項，也就是結果

Code

public int evalRPN(String[] tokens) {
    // Init. stack for the integers
    Stack<Integer> stack = new Stack<>();

    // Iterate through all the tokens
    for (String token : tokens) {
        // Check symbol
        if (token.equals("+")) {
            // Push the result to the stack
            stack.push(stack.pop() + stack.pop());
        } else if (token.equals("-")) {
            int b = stack.pop();
            int a = stack.pop();
            stack.push(a - b);
        } else if (token.equals("*")) {
            stack.push(stack.pop() * stack.pop());
        } else if (token.equals("/")) {
            int b = stack.pop();
            int a = stack.pop();
            stack.push(a / b);
        } else { // If it is a number, parse it and push to the stack
            stack.push(Integer.parseInt(token));
        }
    }
    // Pop the result
    return stack.pop();
}

2024/01/07

• 直覺還是stack，這個沒有問題，這題算是一半依靠之前的submission做出來的
• 這次用switch不知道哪裡有問題，EmptyStackException

以下code snippet是WA

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack();
        
        for (String token : tokens) {
            char firstChar = token.charAt(0);

            switch (firstChar) {
                case '+':
                    stack.push(stack.pop() + stack.pop());
                    break;
                case '-':
                    int latterNum = stack.pop();
                    stack.push(stack.pop()  - latterNum);
                    break;
                case '*':
                    stack.push(stack.pop() * stack.pop());
                    break;
                case '/':
                    int latter1Num = stack.pop();
                    stack.push(stack.pop() / latter1Num);
                    break;
                default: // Number
                    stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
}

2024/01/17

這次用switch做出來了

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack();

        for (int i = 0; i < tokens.length; ++i) {
            switch (tokens[i]) {
                case "+":
                    stack.push(stack.pop() + stack.pop());
                    break;
                case "-":
                    int secondNum = stack.pop();
                    stack.push(stack.pop() - secondNum);
                    break;
                case "*":
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/":
                    int secNum = stack.pop();
                    stack.push(stack.pop() / secNum);
                    break;
                default:
                    stack.push(Integer.valueOf(tokens[i]));

            }
        }

        return stack.pop();
    }
}