150. Evaluate Reverse Polish Notation

Explanation

To solve this problem, we can use a stack to keep track of the operands and perform operations based on the operators encountered in the input array of tokens. We iterate through each token and if the token is an operator, we pop the last two operands from the stack, perform the operation, and push the result back onto the stack. If the token is an operand, we simply push it onto the stack. At the end, the stack will contain only one element which is the final result of the expression.

Algorithm:

Initialize an empty stack to store operands.
Iterate through each token in the input array of tokens.
If the token is an operator, pop the last two operands from the stack, perform the operation, and push the result back onto the stack.
If the token is an operand, push it onto the stack.
At the end, the stack will contain only one element which is the final result of the expression.

Time Complexity: O(n) where n is the number of tokens in the input array. Space Complexity: O(n) where n is the number of tokens in the input array.

View Leetcode Problem

import java.util.Stack;

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        
        for(String token : tokens) {
            if(token.equals("+")) {
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                stack.push(operand1 + operand2);
            } else if(token.equals("-")) {
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                stack.push(operand1 - operand2);
            } else if(token.equals("*")) {
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                stack.push(operand1 * operand2);
            } else if(token.equals("/")) {
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                stack.push(operand1 / operand2);
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        
        return stack.pop();
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Sign in to devexcode.com with google.com

Explanation

Code Editor (Testing phase)

Improve Your Solution