grid47 Exploring patterns and algorithms
Oct 23, 2024
6 min read
Solution to LeetCode 150: Evaluate Reverse Polish Notation Problem
You are given an array of strings tokens that represents an arithmetic expression in Reverse Polish Notation (RPN). Your task is to evaluate the expression and return the result as an integer.
Problem
Approach
Steps
Complexity
Input: The input consists of an array of strings, where each string is either an operand (integer) or an operator (+, -, *, /).
Example: tokens = ["3", "4", "-", "5", "*"]
Constraints:
• 1 <= tokens.length <= 10^4
• tokens[i] is either an operator (+, -, *, /) or an integer between [-200, 200].
Output: The output should be an integer representing the result of evaluating the RPN expression.
Example: Result = -35
Constraints:
• The answer can be represented as a 32-bit integer.
Goal: Evaluate the Reverse Polish Notation expression by using a stack to process operands and operators.
Steps:
• Initialize an empty stack.
• Iterate through the tokens array:
• - If the token is an integer, push it onto the stack.
• - If the token is an operator (+, -, *, /), pop the top two elements from the stack, apply the operator, and push the result back onto the stack.
• At the end of the iteration, the stack will contain only one element, which is the result of the expression.
Goal: The expression will always be valid and can be evaluated.
Steps:
• 1 <= tokens.length <= 10^4
• tokens[i] is an operator (+, -, *, /) or an integer between [-200, 200].
Assumptions:
• The expression will always be valid and contain no division by zero.
• Input: tokens = ["3", "4", "-", "5", "*"]
• Explanation: First, 3 - 4 = -1, then -1 * 5 = -35. So the result is -35.
• Input: tokens = ["2", "3", "*", "4", "+"]
• Explanation: First, 2 * 3 = 6, then 6 + 4 = 10. So the result is 10.
Approach: We can solve this problem using a stack to handle the Reverse Polish Notation (RPN) expression evaluation.
Observations:
• Using a stack is ideal for processing Reverse Polish Notation expressions, as operators act on the most recent operands.
• We need to iterate through the tokens, handling both operands and operators, and update the stack as we go.
Steps:
• Initialize an empty stack.
• For each token in the tokens array, check if it's an operand (integer) or an operator (+, -, *, /).
• If it's an operand, push it onto the stack.
• If it's an operator, pop two operands from the stack, perform the operation, and push the result back onto the stack.
• At the end, the stack will contain the final result.
Empty Inputs:
• There will always be at least one token in the input.
Large Inputs:
• The solution must handle large inputs efficiently, up to 10^4 tokens.
Special Values:
• Handle negative numbers and division truncation towards zero correctly.
Constraints:
• The solution should be efficient in terms of time and space complexity.
intevalRPN(vector<string>& tokens) {
stack<int> stk;
int n = tokens.size();
for(int i =0; i < n; i++) {
if(tokens[i] !="+"&& tokens[i] !="-"&& tokens[i] !="*"&& tokens[i] !="/") {
stk.push(stoi(tokens[i]));
} else {
int x = stk.top(); stk.pop();
int y = stk.top(); stk.pop();
if(tokens[i] =="*"){ stk.push(y * x); }
if(tokens[i] =="/"){ stk.push(y / x); }
if(tokens[i] =="+"){ stk.push(y + x); }
if(tokens[i] =="-"){ stk.push(y - x); }
}
}
return stk.top();
}
1 : Function Definition
intevalRPN(vector<string>& tokens) {
Defines the function `evalRPN` that takes a vector of strings as input (tokens in Reverse Polish Notation) and returns the result of evaluating the expression.
2 : Variable Declaration
stack<int> stk;
Declares a stack `stk` to store intermediate values while processing the RPN expression.
3 : Variable Initialization
int n = tokens.size();
Initializes `n` to the size of the tokens vector, which represents the number of elements in the RPN expression.
4 : Loop Iteration
for(int i =0; i < n; i++) {
Starts a loop to iterate through each token in the RPN expression.
5 : Conditional Check
if(tokens[i] !="+"&&
Checks if the current token is not an operator (i.e., `+`, `-`, `*`, or `/`). If it is not an operator, the token is assumed to be a number.
6 : Conditional Check
tokens[i] !="-"&&
Continues the check for other operators to ensure the current token is not one of the arithmetic operators.
7 : Conditional Check
tokens[i] !="*"&&
Further checks if the current token is not the multiplication operator.
8 : Conditional Check
tokens[i] !="/") {
Checks if the token is not the division operator.
9 : Stack Operation
stk.push(stoi(tokens[i]));
If the token is a number (not an operator), it is converted to an integer using `stoi` and pushed onto the stack.
10 : Else Block
} else {
If the token is an operator, the algorithm proceeds to perform the corresponding arithmetic operation.
11 : Stack Operation
int x = stk.top(); stk.pop();
Pops the top value from the stack and assigns it to `x`. This represents the second operand for the operation.
12 : Stack Operation
int y = stk.top(); stk.pop();
Pops the next value from the stack and assigns it to `y`. This represents the first operand for the operation.
13 : Arithmetic Operation
if(tokens[i] =="*"){ stk.push(y * x); }
Performs multiplication if the current token is the `*` operator. The result is pushed onto the stack.
14 : Arithmetic Operation
if(tokens[i] =="/"){ stk.push(y / x); }
Performs division if the current token is the `/` operator. The result is pushed onto the stack.
15 : Arithmetic Operation
if(tokens[i] =="+"){ stk.push(y + x); }
Performs addition if the current token is the `+` operator. The result is pushed onto the stack.
16 : Arithmetic Operation
if(tokens[i] =="-"){ stk.push(y - x); }
Performs subtraction if the current token is the `-` operator. The result is pushed onto the stack.
17 : Return Value
return stk.top();
Returns the final result, which is the last remaining value on the stack after processing all the tokens.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: We process each token in the input once, so the time complexity is linear in the number of tokens.
Best Case: O(1)
Worst Case: O(n)
Description: The space complexity is O(n) in the worst case due to the stack used for processing the tokens.
