Problem Statement:
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.
Examples:
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].
Approach:
- Initialize a stack to store operands.
- Define operator functions using a map:
- Each key
(+, -, *, /)maps to a function that performs the respective operation on two numbers.
- Each key
- Loop through each token in the input array:
- If the token is an operator:
- Pop the top two values from the stack.
- Convert them to numbers and apply the operator function.
- Push the result back to the stack
- If the token is a number:
- Push it directly to the stack.
- Return the final result by popping the last element from the stack and converting it to a number.
Visualisation:
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input:
arr = ["2", "1", "+", "3", "*"]
State Transitions:
Initialize: stack = []
i = 0 → arr[0] = "2"
→ Not an operator → stack.push("2") → stack = ["2"]
i = 1 → arr[1] = "1"
→ Not an operator → stack.push("1") → stack = ["2", "1"]
i = 2 → arr[2] = "+"
→ Operator found
→ a = stack.pop() = "1"
→ b = stack.pop() = "2"
→ ans = map["+"](1, 2) = 3
→ stack.push(3) → stack = [3]
i = 3 → arr[3] = "3"
→ Not an operator → stack.push("3") → stack = [3, "3"]
i = 4 → arr[4] = ""
→ Operator found
→ a = stack.pop() = "3"
→ b = stack.pop() = 3
→ ans = map[""](3, 3) = 9
→ stack.push(9) → stack = [9]
Final Output: 9
Final State: stack = [] (after popping result)
var evalRPN = function(arr) {
let stack = [];
const map = {
"+": (a,b) => (b+a),
"*": (a,b) => (b*a),
"-": (a,b) => (b-a),
"/": (a,b) => Math.trunc(b/a),
};
for(let i=0; i < arr.length; i++){
if(map[arr[i]]) {
let a = stack.pop();
let b = stack.pop();
let ans = map[arr[i]](+a,+b);
stack.push(ans);
} else {
stack.push(arr[i])
}
}
return Number(stack.pop());
};
def evalRPN(arr):
stack = []
map = {
"+": lambda a, b: b + a,
"-": lambda a, b: b - a,
"*": lambda a, b: b * a,
"/": lambda a, b: int(b / a)
}
for token in arr:
if token in map:
a = stack.pop()
b = stack.pop()
ans = map[token](a, b)
stack.append(ans)
else:
stack.append(int(token))
return stack.pop()
import java.util.*;
public class Solution {
public int evalRPN(String[] arr) {
Stack stack = new Stack<>();
Map> map = new HashMap<>();
map.put("+", (a, b) -> b + a);
map.put("-", (a, b) -> b - a);
map.put("*", (a, b) -> b * a);
map.put("/", (a, b) -> b / a);
for (int i = 0; i < arr.length; i++) {
if (map.containsKey(arr[i])) {
int a = stack.pop();
int b = stack.pop();
int ans = map.get(arr[i]).apply(a, b);
stack.push(ans);
} else {
stack.push(Integer.parseInt(arr[i]));
}
}
return stack.pop();
}
}
#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
int evalRPN(vector& arr) {
stack stack;
unordered_map> map = {
{"+", [](int a, int b) { return b + a; }},
{"*", [](int a, int b) { return b * a; }},
{"-", [](int a, int b) { return b - a; }},
{"/", [](int a, int b) { return b / a; }}
};
for (int i = 0; i < arr.size(); i++) {
if (map.count(arr[i])) {
int a = stack.top(); stack.pop();
int b = stack.top(); stack.pop();
int ans = map[arr[i]](a, b);
stack.push(ans);
} else {
stack.push(stoi(arr[i]));
}
}
return stack.top();
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int evalRPN(char** arr, int size) {
int stack[1000];
int top = -1;
for (int i = 0; i < size; i++) {
if (!strcmp(arr[i], "+") || !strcmp(arr[i], "-") || !strcmp(arr[i], "*") || !strcmp(arr[i], "/")) {
int a = stack[top--];
int b = stack[top--];
int ans;
if (!strcmp(arr[i], "+")) ans = b + a;
else if (!strcmp(arr[i], "-")) ans = b - a;
else if (!strcmp(arr[i], "*")) ans = b * a;
else ans = b / a;
stack[++top] = ans;
} else {
stack[++top] = atoi(arr[i]);
}
}
return stack[top];
}
using System;
using System.Collections.Generic;
public class Solution {
public int EvalRPN(string[] arr) {
Stack stack = new Stack();
Dictionary> map = new Dictionary> {
{ "+", (a, b) => b + a },
{ "-", (a, b) => b - a },
{ "*", (a, b) => b * a },
{ "/", (a, b) => b / a }
};
for (int i = 0; i < arr.Length; i++) {
if (map.ContainsKey(arr[i])) {
int a = stack.Pop();
int b = stack.Pop();
int ans = map[arr[i]](a, b);
stack.Push(ans);
} else {
stack.Push(int.Parse(arr[i]));
}
}
return stack.Pop();
}
}
