Evaluate Reverse Polish Notation

                                            
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(string token : tokens){
            if(token == "+"){
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();
                st.push(num1 + num2);
            } else if(token == "-"){
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();
                st.push(num2 - num1);
            } else if(token == "*"){
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();
                st.push(num1 * num2);
            } else if(token == "/"){
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();
                st.push(num2 / num1);
            } else {
                st.push(stoi(token));
            }
        }
        return st.top();
    }
};

                                            
import java.util.Stack;

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            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 (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 {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
}

                                            
class Solution(object):
    def evalRPN(self, tokens):
        stack = []
        for token in tokens:
            if token not in ['+', '-', '*', '/']:
                stack.append(int(token))
            else:
                num2 = stack.pop()
                num1 = stack.pop()
                if token == '+':
                    stack.append(num1 + num2)
                elif token == '-':
                    stack.append(num1 - num2)
                elif token == '*':
                    stack.append(num1 * num2)
                else:
                    stack.append(int(float(num1) / num2))
        return stack[0]

                                            
typedef struct {
    int top;
    int capacity;
    int* array;
} Stack;

Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
    return stack;
}

int isEmpty(Stack* stack) {
    return stack->top == -1;
}

void push(Stack* stack, int item) {
    stack->array[++stack->top] = item;
}

int pop(Stack* stack) {
    return stack->array[stack->top--];
}

int evalRPN(char** tokens, int tokensSize) {
    Stack* stack = createStack(tokensSize);
    for (int i = 0; i < tokensSize; i++) {
        if (strcmp(tokens[i], "+") == 0) {
            int a = pop(stack);
            int b = pop(stack);
            push(stack, b + a);
        } else if (strcmp(tokens[i], "-") == 0) {
            int a = pop(stack);
            int b = pop(stack);
            push(stack, b - a);
        } else if (strcmp(tokens[i], "*") == 0) {
            int a = pop(stack);
            int b = pop(stack);
            push(stack, b * a);
        } else if (strcmp(tokens[i], "/") == 0) {
            int a = pop(stack);
            int b = pop(stack);
            push(stack, b / a);
        } else {
            push(stack, atoi(tokens[i]));
        }
    }
    int result = pop(stack);
    free(stack->array);
    free(stack);
    return result;
}

                                            
public class Solution {
    public int EvalRPN(string[] tokens) {
        Stack<int> stack = new Stack<int>();

        foreach (string token in tokens) {
            if (token == "+") {
                int num2 = stack.Pop();
                int num1 = stack.Pop();
                stack.Push(num1 + num2);
            } else if (token == "-") {
                int num2 = stack.Pop();
                int num1 = stack.Pop();
                stack.Push(num1 - num2);
            } else if (token == "*") {
                int num2 = stack.Pop();
                int num1 = stack.Pop();
                stack.Push(num1 * num2);
            } else if (token == "/") {
                int num2 = stack.Pop();
                int num1 = stack.Pop();
                stack.Push(num1 / num2);
            } else {
                stack.Push(int.Parse(token));
            }
        }

        return stack.Pop();
    }
}

                                            
/**
 * @param {string[]} tokens
 * @return {number}
 */
const evalRPN = function(tokens) {
    const stack = [];
    for (let token of tokens) {
        if (!isNaN(parseInt(token))) {
            stack.push(parseInt(token));
        } else {
            const num2 = stack.pop();
            const num1 = stack.pop();
            if (token === '+') {
                stack.push(num1 + num2);
            } else if (token === '-') {
                stack.push(num1 - num2);
            } else if (token === '*') {
                stack.push(num1 * num2);
            } else if (token === '/') {
                stack.push(parseInt(num1 / num2));
            }
        }
    }
    return stack.pop();
};

                                            
function evalRPN(tokens: string[]): number {
    const stack: number[] = [];
    const operators = new Set(['+', '-', '*', '/']);
    
    for (const token of tokens) {
        if (operators.has(token)) {
            const num2 = stack.pop()!;
            const num1 = stack.pop()!;
            if (token === '+') stack.push(num1 + num2);
            if (token === '-') stack.push(num1 - num2);
            if (token === '*') stack.push(num1 * num2);
            if (token === '/') stack.push(Math.trunc(num1 / num2));
        } else {
            stack.push(+token);
        }
    }
    
    return stack[0];
};

                                            
class Solution {
    /**
     * @param String[] $tokens
     */
    function evalRPN($tokens) {
        $stack = [];
        $operators = ['+', '-', '*', '/'];
        
        foreach ($tokens as $token) {
            if (in_array($token, $operators)) {
                $operand2 = array_pop($stack);
                $operand1 = array_pop($stack);
                
                if ($token == '+') {
                    array_push($stack, $operand1 + $operand2);
                } elseif ($token == '-') {
                    array_push($stack, $operand1 - $operand2);
                } elseif ($token == '*') {
                    array_push($stack, $operand1 * $operand2);
                } elseif ($token == '/') {
                    array_push($stack, intval($operand1 / $operand2));
                }
            } else {
                array_push($stack, intval($token));
            }
        }
        
        return $stack[0];
    }
}

To solve this coding challenge, we need to evaluate an arithmetic expression given in Reverse Polish Notation (RPN). RPN is a mathematical notation wherein every operator follows all of its operands, making the order of operations clear and unambiguous without needing parentheses.

Explanation

The methodology involves using a stack to keep track of operands until an operator is encountered. When an operator is encountered, the necessary number of operands are popped from the stack, the operation is performed, and the result is pushed back onto the stack. At the end of the evaluation, the stack will contain the final output of the expression. Here is a step-by-step explanation along with pseudocode for evaluating the RPN expression:

Initialize a Stack : We start by creating an empty stack. This will be used to store the operands.
Iterate through Tokens : We iterate through each element in the input list
tokens

. If the element is an operator, we pop the necessary number of operands from the stack, apply the operator, and push the result back onto the stack. If the element is an operand, we push it onto the stack.
Pop Operands for Operators : For each operator, pop the top two elements from the stack, perform the arithmetic operation, and push the result back onto the stack. Ensure to handle integer division correctly by truncating towards zero.
Final Result : After the entire input list has been processed, the stack should contain only one element, which is the final result of the evaluated expression.

Detailed Steps in Pseudocode

Here's the pseudocode with comments to illustrate the logic:

                                            
# Pseudocode for evaluating Reverse Polish Notation

# Function to evaluate RPN
function evaluateRPN(tokens):
# Initialize an empty stack to store operands
stack = []

# Iterate over each token in the input list
for token in tokens:
# Check if the token is an operator
if token in ["+", "-", "*", "/"]:
# Pop the top two operands from the stack
operand2 = stack.pop()
operand1 = stack.pop()

# Perform the corresponding operation and push the result back into the stack
if token == "+":
result = operand1 + operand2
stack.append(result)
elif token == "-":
result = operand1 - operand2
stack.append(result)
elif token == "*":
result = operand1 * operand2
stack.append(result)
elif token == "/":
# Perform integer division and truncate towards zero
result = int(operand1 / operand2)
stack.append(result)
else:
# If the token is an operand, convert it to an integer and push it onto the stack
operand = int(token)
stack.append(operand)

# The final result of the RPN expression is the last element in the stack
return stack[0]

# Example usage:
# tokens = ["2", "1", "+", "3", "*"]
# Output of evaluateRPN(tokens) should be 9

Step-by-step Explanation:

Initialization :

Create an empty stack named
stack

.

Iteration :

Loop through each item in the
tokens

list.
For each item:

If the item is an operand, convert it to an integer and push it onto
stack

.
If the item is an operator:

Pop the top two operands from
stack

.
Perform the appropriate arithmetic operation (
+

,
-

,
*

,
/

).
Push the result of the operation back onto
stack

.

Operator Handling :

When encountering
+

, pop two elements, add them, and push the result.
When encountering
-

, pop two elements, subtract the second popped element from the first, and push the result.
When encountering
*

, pop two elements, multiply them, and push the result.
When encountering
/

, pop two elements, perform integer division of the first popped element by the second, converting the result to integer, and push the result.

Final Outcome :

Once all tokens have been processed, the only remaining element in
stack

is the result of the Reverse Polish Notation expression.
Return this single element.

By following these detailed steps and the provided pseudocode, you should be able to evaluate any valid Reverse Polish Notation expression accurately.