hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Evaluate Reverse Polish Notation
Problem: 150. Evaluate Reverse Polish Notation
Problem Link: leetcode.com/problems/evaluate-reverse-polish-notation/
Companies Asked: Google, LinkedIn, Amazon, Microsoft, Facebook, Oracle, Yandex
Approach:
Firstly, traverse the vector and access each string.
Instantiated a stack of integers.
For each string, checked if it is an operator or a number.
If we encounter an operator, then popped very two top elements and did the operation accordingly.
If we encounter a number, then entered it into the stack.
Repeat the process until we reach at the end of traversing the given vector.
Returned the top integer.
Time and Space Complexity:
Time complexity: O(n)
Space complexity: O(n)
n = size of the given vector.
Code [C++]
class Solution {
public:
int to_int(string & number){
int result = 0, n = number.size(), i = 0;
if(number[i] == '-') i++;
while(i < n){
result *= 10;
result += (number[i++] - '0');
}
if(number[0] == '-') result = -result;
return result;
}
int evalRPN(vector<string>& tokens) {
int n = tokens.size();
stack<long long>op_str;
int i = 0;
while(i<n){
if(tokens[i]!="+" && tokens[i]!="-" && tokens[i]!="*" && tokens[i]!="/"){
int number = to_int(tokens[i]);
op_str.push((long long)number);
}
else{
long long op1 = op_str.top(); op_str.pop();
long long op2 = op_str.top(); op_str.pop();
long long result;
if(tokens[i] == "+"){
result = op1 + op2;
}
else if(tokens[i] == "-"){
result = op2 - op1;
}
else if(tokens[i] == "*"){
result = op1 * op2;
}
else result = op2 / op1;
op_str.push(result);
}
i++;
}
return op_str.top();
}
};