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


  • Approach:

    1. Firstly, traverse the vector and access each string.

    2. Instantiated a stack of integers.

    3. For each string, checked if it is an operator or a number.

    4. If we encounter an operator, then popped very two top elements and did the operation accordingly.

    5. If we encounter a number, then entered it into the stack.

    6. Repeat the process until we reach at the end of traversing the given vector.

    7. 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();

}

};