# Solution For Evaluate Reverse Polish Notation

The idea of the Evaluate Reverse Polish Notation problem is to evaluate an arithmetic expression in Reverse Polish Notation (RPN), which can be done using a stack data structure. In RPN, operators come after their operands, so for example, the expression “3 + 4” in infix notation becomes “3 4 +” in RPN.

Here’s a step-by-step solution to the problem:

1. Initialize an empty stack.
2. For each element in the input string:
3. If the element is a number, push it onto the stack.
4. If the element is an operator (+, -, *, /), pop two elements from the stack, apply the operator to them in postfix order (the second element popped is the right operand), and push the result onto the stack.
5. After processing all elements in the input string, the top of the stack should contain the final result. Pop it from the stack and return it.

Here’s the implementation of this algorithm in Python:

```python class Solution: def evalRPN(self, tokens: List[str]) -> int: stack = [] for token in tokens: if token.isdigit() or (token == "-" and token[1:].isdigit()): stack.append(int(token)) else: op2 = stack.pop() op1 = stack.pop() if token == "+": stack.append(op1 + op2) elif token == "-": stack.append(op1 - op2) elif token == "*": stack.append(op1 * op2) else: stack.append(int(op1 / op2)) return stack.pop()```

In this implementation, we first check whether each token is a number (positive or negative) by checking its first character. If so, we convert it to an integer and push it onto the stack. Otherwise, we assume it’s an operator and pop two operands from the stack to apply the operator to. We use `int(op1 / op2)` instead of just `op1 / op2` to handle integer division properly (e.g., `1 / -1` should be `-1`, not `-1.0`). Finally, we return the result by popping it from the stack.

This solution has a time complexity of O(n), where n is the length of the input string. We iterate over each element once and perform constant-time operations on the stack. It also has a space complexity of O(n) in the worst case if all elements are numbers and they’re all pushed onto the stack.

## Step by Step Implementation For Evaluate Reverse Polish Notation

```import java.util.*;

public class Solution {
public int evalRPN(String[] tokens) {
Stack stack = new Stack<>();
for(String s : tokens){
if(s.equals("+")){
stack.push(stack.pop()+stack.pop());
}else if(s.equals("-")){
stack.push(-stack.pop()+stack.pop());
}else if(s.equals("*")){
stack.push(stack.pop()*stack.pop());
}else if(s.equals("/")){
int num1 = stack.pop();
stack.push(stack.pop()/num1);
}else{
stack.push(Integer.parseInt(s));
}
}
return stack.pop();
}
}```
```class Solution:
def evalRPN(self, tokens: List[str]) -> int:

# create a stack to store the operands
stack = []

# loop through all the tokens
for t in tokens:

# if the token is an operator
if t in ["+", "-", "*", "/"]:

# pop the top two elements from the stack
a = stack.pop()
b = stack.pop()

# perform the operation
if t == "+":
stack.append(a+b)
elif t == "-":
stack.append(b-a)
elif t == "*":
stack.append(a*b)
else:
stack.append(int(b/a))

# if the token is an operand
else:
# push it onto the stack
stack.append(int(t))

# return the top of the stack
return stack[-1]```
```var evalRPN = function(tokens) {
// create a stack
let stack = [];

// iterate over the tokens array
for (let i = 0; i < tokens.length; i++) {
// if the current token is an operator
if (tokens[i] === '+' || tokens[i] === '-' || tokens[i] === '*' || tokens[i] === '/') {
// pop the top two elements from the stack
let a = stack.pop();
let b = stack.pop();

// perform the operation on the two popped elements
// and push the result back onto the stack
if (tokens[i] === '+') {
stack.push(a + b);
} else if (tokens[i] === '-') {
stack.push(b - a);
} else if (tokens[i] === '*') {
stack.push(a * b);
} else if (tokens[i] === '/') {
stack.push(Math.floor(b / a));
}
// if the current token is not an operator,
// simply push it onto the stack
} else {
stack.push(parseInt(tokens[i]));
}
}

// return the top element of the stack
// this will be the final answer
return stack;
};```
```#include
#include
#include
using namespace std;

class Solution {
public:
int evalRPN(vector& tokens) {
stack s;
for(int i=0;iusing System;
using System.Collections.Generic;

public class GFG {

// Method to evaluate value of a postfix expression
static int EvaluatePostfix(string exp)
{

//create a stack
Stack stack=new Stack();

// Scan all characters one by one
for(int i=0;i```
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]