## Algorithm

Problem Name: 150. Evaluate Reverse Polish Notation

You are given an array of strings `tokens` that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

• The valid operators are `'+'`, `'-'`, `'*'`, and `'/'`.
• Each operand may be an integer or another expression.
• The division between two integers always truncates toward zero.
• There will not be any division by zero.
• The input represents a valid arithmetic expression in a reverse polish notation.
• The answer and all the intermediate calculations can be represented in a 32-bit integer.

Example 1:

```Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
```

Example 2:

```Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
```

Example 3:

```Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
```

Constraints:

• `1 <= tokens.length <= 104`
• `tokens[i]` is either an operator: `"+"`, `"-"`, `"*"`, or `"/"`, or an integer in the range `[-200, 200]`.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node {
int val;
struct Node *next;
};

void push(struct Node** top_pt, int new_data)
{
struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
new_node->val = new_data;
new_node->next = *top_pt;

*top_pt = new_node;
}

int pop(struct Node** top_pt)
{
if (*top_pt == NULL)
{
printf("stack overflow\n");
exit(0);
}
struct Node *top = *top_pt;
int res = top->val;
*top_pt = top->next;
free(top);
return res;
}

int evalRPN(char *tokens[], int n) {
struct Node *stack = NULL;
int i;
for (i = 0; i < n; i++)
{
if (strcmp(tokens[i], "+") == 0) {
int r = pop(&stack);
int l = pop(&stack);
push(&stack, l + r);
}
else if (strcmp(tokens[i], "-") == 0) {
int r = pop(&stack);
int l = pop(&stack);
push(&stack, l - r);
}
else if (strcmp(tokens[i], "*") == 0) {
int r = pop(&stack);
int l = pop(&stack);
push(&stack, l * r);
}
else if (strcmp(tokens[i], "/") == 0) {
int r = pop(&stack);
int l = pop(&stack);
push(&stack, l / r);
}
else
push(&stack, atoi(tokens[i]));
}
return pop(&stack);
}

void print_stack(struct Node** top_pt)
{
struct Node *t = *top_pt;
while (t != NULL)
{
struct Node *tmp_node = t;
printf("%d ", tmp_node->val);
t = tmp_node->next;
}
printf("\n");
}

int main()
{
char *tokens[] = {"3","-4","+"};
printf("%d\n", evalRPN(tokens, sizeof(tokens)/ sizeof(tokens[0])));
return 0;
}
``````
Copy The Code &

Input

cmd
tokens = ["2","1","+","3","*"]

Output

cmd
9

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {

private static final Set OPERATIONS = Set.of("*", "+", "/", "-");

public int evalRPN(String[] tokens) {
Stack stack = new Stack<>();
for (String token : tokens) {
if (OPERATIONS.contains(token)) {
stack.push(performOperation(stack.pop(), stack.pop(), token));
} else {
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}

private static int performOperation(int num2, int num1, String operation) throws UnsupportedOperationException {
return switch(operation) {
case "+" -> num1 + num2;
case "-" -> num1 - num2;
case "*" -> num1 * num2;
case "/" -> num1 / num2;
default -> throw new UnsupportedOperationException("Operation not supported");
};
}
}
``````
Copy The Code &

Input

cmd
tokens = ["2","1","+","3","*"]

Output

cmd
9

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const evalRPN = function(tokens) {
const stack = []
for (let token of tokens) {
if (token === '+') {
stack.push(stack.pop() + stack.pop())
} else if (token === '-') {
stack.push(-stack.pop() + stack.pop())
} else if (token === '*') {
stack.push(stack.pop() * stack.pop())
} else if (token === '/') {
stack.push(Math.trunc((1 / stack.pop()) * stack.pop()))
} else {
stack.push(parseInt(token))
}
}
return stack[0]
}
``````
Copy The Code &

Input

cmd
tokens = ["4","13","5","/","+"]

Output

cmd
6

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def evalRPN(self, tokens):
"""
:type tokens: List[str]
:rtype: int
"""
stack = []
for token in tokens:
if token not in ("+", "-", "*", "/"): stack.append(int(token))
else:
num2, num1 = stack.pop(), stack.pop()
if token == "+": last = num1 + num2
elif token == "-": last = num1 - num2
elif token == "*": last = num1 * num2
elif token == "/": last = int(num1 / num2)
stack.append(last)
return stack[0]
``````
Copy The Code &

Input

cmd
tokens = ["4","13","5","/","+"]

Output

cmd
6