Dare2Solve
Reverse Polish Notation (RPN) is a mathematical notation in which every operator follows all of its operands. It is also known as postfix notation. To evaluate an expression in RPN, a stack is used to store operands, and operators are applied to the operands in the correct order. This approach naturally fits the stack data structure, as it allows easy management of operands and operators.
Initialization:
Iteration:
tokens
:
+
, -
, *
, /
), pop the top two operands from the stack, apply the operator, and push the result back onto the stack.Operations:
val2
be the first popped element and val1
be the second.val1
and val2
:
+
, push val1 + val2
.-
, push val1 - val2
.*
, push val1 * val2
./
, push int(val1 / val2)
to ensure truncation towards zero.Final Result:
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> stack;
for (const string& token : tokens) {
if (isdigit(token.back())) {
stack.push(stoi(token));
} else {
int val2 = stack.top();
stack.pop();
int val1 = stack.top();
stack.pop();
int result;
switch (token[0]) {
case '*':
result = val1 * val2;
break;
case '+':
result = val1 + val2;
break;
case '-':
result = val1 - val2;
break;
case '/':
result = val1 / val2;
break;
}
stack.push(result);
}
}
return stack.top();
}
};
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for token in tokens:
if token.lstrip('-').isdigit():
stack.append(int(token))
else:
val2 = stack.pop()
val1 = stack.pop()
if token == '*':
stack.append(val1 * val2)
elif token == '+':
stack.append(val1 + val2)
elif token == '-':
stack.append(val1 - val2)
elif token == '/':
stack.append(int(val1 / val2))
return stack.pop()
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
if (isNumeric(token)) {
stack.push(Integer.parseInt(token));
} else {
int val2 = stack.pop();
int val1 = stack.pop();
int result;
switch (token) {
case "*":
result = val1 * val2;
break;
case "+":
result = val1 + val2;
break;
case "-":
result = val1 - val2;
break;
case "/":
result = val1 / val2;
break;
default:
throw new IllegalArgumentException("Invalid operator: " + token);
}
stack.push(result);
}
}
return stack.pop();
}
private boolean isNumeric(String str) {
try {
Integer.parseInt(str);
return true;
} catch (NumberFormatException e) {
return false;
}
}
}
var evalRPN = function (tokens) {
let stack = [];
for (let i = 0; i < tokens.length; i++)
{
let val = Number(tokens[i]);
if (!isNaN(val)) {
stack.push(val)
} else {
let val = stack.pop();
let val1 = stack.pop();
switch (tokens[i]) {
case '*':
out = val1 * val
break;
case '+':
out = val1 + val
break;
case '-':
out = val1 - val
break;
case '/':
out = Math.trunc(val1 / val)
break;
}
stack.push(out)
}
}
return stack.pop()
};