C++ O(n) solution :)


#1

int evaluate(string n1,string oper,string n2)
{
int num1 = stoi(n1);
int num2 = stoi(n2);
if(oper == "")
return num1
num2;
if(oper == “/”)
return num1/num2;
if(oper == “-”)
return num1-num2;
if(oper == “+”)
return num1+num2;

}

bool isNumber(string ch)
{
if(ch!="+"&&ch!="-"&&ch!="/"&&ch!="*")
return true;
return false;
}

int Solution::evalRPN(vector &A) {

int n = A.size();
stack<string> s;
int curr_count = 0;//this keep count of consecutive numbers in stack;
for(int i=n-1;i>=0;i--)
{
   
    s.push(A[i]);//put value in stack
 
   if(isNumber(A[i]))//if number found
    {
        curr_count++;
    }
    else//if operator found
    {
        curr_count=0;
    }
    while(curr_count==2)//if we get 2 consecutive numbers are in the stack evaluate that 
    {                   //push evaluated number in stack;
        string num1 = s.top();
        s.pop();
        string num2 = s.top();
        s.pop();
        string oper = s.top();
        s.pop();
       int val = evaluate(num1,oper,num2);
       if(!s.empty()){
        if(isNumber(s.top()))
           curr_count =2;
        else
           curr_count = 1;
       }
       else
       {
           return val;//if stack is empty return evaluated number.
       }
        s.push(to_string(val));
    }
}
int ans =stoi(s.top());//else return stack top
return ans;

}