Evaluate Reverse Polish Notation
Program for Evaluating Reverse Polish Notation Problem
You are provided with an array of strings, tokens, which represents a valid arithmetic expression in Reverse Polish Notation.
Your task is to calculate and return the integer result of evaluating the expression.
- The operands in the expression can either be integers or the results of previous operations.
- The supported operators are +, -, *, and /.
- Assume that any division operation between integers truncates the result toward zero.
Example 1
Input: tokens = ["1","2","+","3","*","4","-"]
Output: 5
Output: 5
Explanation: ((1 + 2) * 3) – 4 = 5
Constraints:
- 1 <= tokens.length <= 1000.
- tokens[i] is “+”, “-“, “*”, or “/”, or a string representing an integer in the range [-100, 100].
Program for Evaluating Reverse Polish Notation Solution
Recommendation for Time and Space Complexity –You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.
Hints for solving problems
Hint 1 :
A brute force approach would involve repeatedly identifying an operator (+, -, *, /) in the array, computing the result using the operator and its two preceding operands, and replacing these elements in the array. However, this results in an O(n^2) time complexity. Can you think of a more efficient solution? Perhaps a specific data structure could simplify the process.
Hint 2 :
A stack can be used to solve this efficiently. As we traverse the array, we push numbers onto the stack. When an operator is encountered, we pop the top two elements from the stack, perform the operation, and push the result back onto the stack. This ensures the correct order of operations is maintained.
Hint 3 :
Since the array represents a postfix expression, the stack effectively manages the order of operations by always utilizing the most recent operands (those nearest the operator). After completing the iteration, the final result will be the only element left in the stack.
There are mainly 4 approach to solve this problem-
- Brute Force Method
- Doubly Linked List Method
- Recursion Method
- Stack Method
1. Brute Force Method
Traverse the array repeatedly to identify operators, calculate results using the operator and its operands, and replace them in the array, resulting in O(n^2) time complexity.
- Time complexity: O(n^2)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int evalRPN(vector<string>& tokens) {
while (tokens.size() > 1) {
for (int i = 0; i < tokens.size(); i++) {
if (tokens[i] == "+"
|| tokens[i] == "-"
|| tokens[i] == "*"
|| tokens[i] == "/")
{
int a = stoi(tokens[i - 2]);
int b = stoi(tokens[i - 1]);
int result = 0;
if (tokens[i] == "+") result = a + b;
else if (tokens[i] == "-") result = a - b;
else if (tokens[i] == "*") result = a * b;
else if (tokens[i] == "/") result = a / b;
tokens.erase(tokens.begin() + i - 2, tokens.begin() + i + 1);
tokens.insert(tokens.begin() + i - 2, to_string(result));
break;
}
}
}
return stoi(tokens[0]);
}
};
Java
public class Solution {
public int evalRPN(String[] tokens) {
List<String> tokenList = new ArrayList<>(Arrays.asList(tokens));
while (tokenList.size() > 1) {
for (int i = 0; i < tokenList.size(); i++) {
String token = tokenList.get(i);
if ("+-*/".contains(token)) {
int a = Integer.parseInt(tokenList.get(i - 2));
int b = Integer.parseInt(tokenList.get(i - 1));
int result = 0;
if (token.equals("+")) {
result = a + b;
} else if (token.equals("-")) {
result = a - b;
} else if (token.equals("*")) {
result = a * b;
} else if (token.equals("/")) {
result = a / b;
}
tokenList.set(i - 2, String.valueOf(result));
tokenList.remove(i);
tokenList.remove(i - 1);
break;
}
}
}
return Integer.parseInt(tokenList.get(0));
}
}
Python
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
while len(tokens) > 1:
for i in range(len(tokens)):
if tokens[i] in "+-*/":
a = int(tokens[i-2])
b = int(tokens[i-1])
if tokens[i] == '+':
result = a + b
elif tokens[i] == '-':
result = a - b
elif tokens[i] == '*':
result = a * b
elif tokens[i] == '/':
result = int(a / b)
tokens = tokens[:i-2] + [str(result)] + tokens[i+1:]
break
return int(tokens[0])
JavaScript
class Solution {
evalRPN(tokens) {
while (tokens.length > 1) {
for (let i = 0; i < tokens.length; i++) {
if ("+-*/".includes(tokens[i])) {
const a = parseInt(tokens[i - 2]);
const b = parseInt(tokens[i - 1]);
let result;
if (tokens[i] === "+") result = a + b;
else if (tokens[i] === "-") result = a - b;
else if (tokens[i] === "*") result = a * b;
else if (tokens[i] === "/") result = Math.trunc(a / b);
tokens.splice(i - 2, 3, result.toString());
break;
}
}
}
return parseInt(tokens[0]);
}
}
2. Doubly Linked List Method
Use a doubly linked list to store tokens, enabling efficient insertion and deletion of elements while calculating results for operators encountered during traversal.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class DoublyLinkedList {
public:
string val;
DoublyLinkedList* next;
DoublyLinkedList* prev;
DoublyLinkedList(string val, DoublyLinkedList* next = nullptr,
DoublyLinkedList* prev = nullptr) {
this->val = val;
this->next = next;
this->prev = prev;
}
};
class Solution {
public:
int evalRPN(vector& tokens) {
DoublyLinkedList* head = new DoublyLinkedList(tokens[0]);
DoublyLinkedList* curr = head;
for (int i = 1; i < tokens.size(); i++) {
curr->next = new DoublyLinkedList(tokens[i], nullptr, curr);
curr = curr->next;
}
int ans = 0;
while (head != nullptr) {
if (head->val == "+" ||
head->val == "-" ||
head->val == "*" ||
head->val == "/")
{
int l = stoi(head->prev->prev->val);
int r = stoi(head->prev->val);
int res = 0;
if (head->val == "+") {
res = l + r;
} else if (head->val == "-") {
res = l - r;
} else if (head->val == "*") {
res = l * r;
} else {
res = l / r;
}
head->val = to_string(res);
head->prev = head->prev->prev->prev;
if (head->prev != nullptr) {
head->prev->next = head;
}
}
ans = stoi(head->val);
head = head->next;
}
return ans;
}
};
Java
public class DoublyLinkedList {
String val;
DoublyLinkedList next;
DoublyLinkedList prev;
DoublyLinkedList(String val, DoublyLinkedList next, DoublyLinkedList prev) {
this.val = val;
this.next = next;
this.prev = prev;
}
}
public class Solution {
public int evalRPN(String[] tokens) {
DoublyLinkedList head = new DoublyLinkedList(tokens[0], null, null);
DoublyLinkedList curr = head;
for (int i = 1; i < tokens.length; i++) {
curr.next = new DoublyLinkedList(tokens[i], null, curr);
curr = curr.next;
}
int ans = 0;
while (head != null) {
if ("+-*/".contains(head.val)) {
int l = Integer.parseInt(head.prev.prev.val);
int r = Integer.parseInt(head.prev.val);
int res = 0;
if (head.val.equals("+")) {
res = l + r;
} else if (head.val.equals("-")) {
res = l - r;
} else if (head.val.equals("*")) {
res = l * r;
} else {
res = l / r;
}
head.val = String.valueOf(res);
head.prev = head.prev.prev.prev;
if (head.prev != null) {
head.prev.next = head;
}
}
ans = Integer.parseInt(head.val);
head = head.next;
}
return ans;
}
}
Python
class DoublyLinkedList:
def __init__(self, val, next=None, prev=None):
self.val = val
self.next = next
self.prev = prev
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
head = DoublyLinkedList(tokens[0])
curr = head
for i in range(1, len(tokens)):
curr.next = DoublyLinkedList(tokens[i], prev=curr)
curr = curr.next
while head is not None:
if head.val in "+-*/":
l = int(head.prev.prev.val)
r = int(head.prev.val)
if head.val == '+':
res = l + r
elif head.val == '-':
res = l - r
elif head.val == '*':
res = l * r
else:
res = int(l / r)
head.val = str(res)
head.prev = head.prev.prev.prev
if head.prev is not None:
head.prev.next = head
ans = int(head.val)
head = head.next
return ans
JavaScript
class DoublyLinkedList {
constructor(val, next = null, prev = null) {
this.val = val;
this.next = next;
this.prev = prev;
}
}
class Solution {
/**
* @param {string[]} tokens
* @return {number}
*/
evalRPN(tokens) {
let head = new DoublyLinkedList(tokens[0]);
let curr = head;
for (let i = 1; i < tokens.length; i++) {
curr.next = new DoublyLinkedList(tokens[i], null, curr);
curr = curr.next;
}
let ans = 0;
while (head !== null) {
if ("+-*/".includes(head.val)) {
let l = parseInt(head.prev.prev.val);
let r = parseInt(head.prev.val);
let res = 0;
if (head.val === "+") {
res = l + r;
} else if (head.val === "-") {
res = l - r;
} else if (head.val === "*") {
res = l * r;
} else {
res = Math.trunc(l / r);
}
head.val = res.toString();
head.prev = head.prev.prev.prev;
if (head.prev !== null) {
head.prev.next = head;
}
}
ans = parseInt(head.val);
head = head.next;
}
return ans;
}
}
3. Recursion Method
Process the tokens recursively, where each operator triggers recursive calls to evaluate its operands, working backward through the array to maintain the correct order.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int dfs(vector<string>& tokens) {
string token = tokens.back();
tokens.pop_back();
if (token != "+" && token != "-" &&
token != "*" && token != "/")
{
return stoi(token);
}
int right = dfs(tokens);
int left = dfs(tokens);
if (token == "+") {
return left + right;
} else if (token == "-") {
return left - right;
} else if (token == "*") {
return left * right;
} else {
return left / right;
}
}
int evalRPN(vector& tokens) {
return dfs(tokens);
}
};
Java
public class Solution {
public int evalRPN(String[] tokens) {
List<String> tokenList = new ArrayList<>(Arrays.asList(tokens));
return dfs(tokenList);
}
private int dfs(List tokens) {
String token = tokens.remove(tokens.size() - 1);
if (!"+-*/".contains(token)) {
return Integer.parseInt(token);
}
int right = dfs(tokens);
int left = dfs(tokens);
switch (token) {
case "+":
return left + right;
case "-":
return left - right;
case "*":
return left * right;
case "/":
return left / right;
}
return 0;
}
}
Python
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
def dfs():
token = tokens.pop()
if token not in "+-*/":
return int(token)
right = dfs()
left = dfs()
if token == '+':
return left + right
elif token == '-':
return left - right
elif token == '*':
return left * right
elif token == '/':
return int(left / right)
return dfs()
JavaScript
class Solution {
/**
* @param {string[]} tokens
* @return {number}
*/
evalRPN(tokens) {
/**
* @return {number}
*/
const dfs = () => {
const token = tokens.pop();
if (!"+-*/".includes(token)) {
return parseInt(token);
}
const right = dfs();
const left = dfs();
if (token === '+') {
return left + right;
} else if (token === '-') {
return left - right;
} else if (token === '*') {
return left * right;
} else {
return Math.trunc(left / right);
}
};
return dfs();
}
}
4. Stack Method
Iterate through the tokens, pushing numbers onto the stack. When encountering an operator, pop two numbers, compute the result, and push it back onto the stack, ensuring O(n) time complexity.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int dfs(vector<string>& tokens) {
string token = tokens.back();
tokens.pop_back();
if (token != "+" && token != "-" &&
token != "*" && token != "/")
{
return stoi(token);
}
int right = dfs(tokens);
int left = dfs(tokens);
if (token == "+") {
return left + right;
} else if (token == "-") {
return left - right;
} else if (token == "*") {
return left * right;
} else {
return left / right;
}
}
int evalRPN(vector& tokens) {
return dfs(tokens);
}
};
Java
public class Solution {
public int evalRPN(String[] tokens) {
List<String> tokenList = new ArrayList<>(Arrays.asList(tokens));
return dfs(tokenList);
}
private int dfs(List tokens) {
String token = tokens.remove(tokens.size() - 1);
if (!"+-*/".contains(token)) {
return Integer.parseInt(token);
}
int right = dfs(tokens);
int left = dfs(tokens);
switch (token) {
case "+":
return left + right;
case "-":
return left - right;
case "*":
return left * right;
case "/":
return left / right;
}
return 0;
}
}
Python
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
def dfs():
token = tokens.pop()
if token not in "+-*/":
return int(token)
right = dfs()
left = dfs()
if token == '+':
return left + right
elif token == '-':
return left - right
elif token == '*':
return left * right
elif token == '/':
return int(left / right)
return dfs()
JavaScript
class Solution {
/**
* @param {string[]} tokens
* @return {number}
*/
evalRPN(tokens) {
/**
* @return {number}
*/
const dfs = () => {
const token = tokens.pop();
if (!"+-*/".includes(token)) {
return parseInt(token);
}
const right = dfs();
const left = dfs();
if (token === '+') {
return left + right;
} else if (token === '-') {
return left - right;
} else if (token === '*') {
return left * right;
} else {
return Math.trunc(left / right);
}
};
return dfs();
}
}
