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 <= 104tokens[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;
}
Input
tokens = ["2","1","+","3","*"]
Output
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 < Integer> 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");
};
}
}
Input
tokens = ["2","1","+","3","*"]
Output
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]
}
Input
tokens = ["4","13","5","/","+"]
Output
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]
Input
tokens = ["4","13","5","/","+"]
Output
6