# Accepted C++ recursive solution (56 ms) with explanation. Simplest possible?

• Algorithm:

1. pop string from the end of the vector

2. if it's number, just return it

3. if it's operation, call function recursively for 2nd operand and 1st

int evalRPN(vector<string> &n) {
string s = n.back(); n.pop_back();
if ( s== "" || s=="/" || s=="+" || s == "-" ){
int r2 = evalRPN(n);
int r1 = evalRPN(n);
if ( s=="
") return r1*r2;
if ( s=="/") return r1/r2;
if ( s=="+") return r1+r2;
if ( s=="-") return r1-r2;
}
else
return atoi(s.c_str());
}

• C++ 11 has a stoi() function, so just return stoi(s)

• Would you mind implementing it in java pls? I don't know how by to pass the "missing return statement" compilation error in Java.

``````public int evalRPN(String[] tokens) {
return helper(tokens, tokens.length-1);
}

int helper(String[] tokens, int top)
{
String t = tokens[top];
top--;
if(t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/"))
{
int n0 = helper(tokens, top);
int n1 = helper(tokens, top);

if(t=="+") return n1+n0;
if(t=="-") return n1-n0;
if(t=="*") return n1*n0;
if(t=="/") return n1/n0;
}
else{
return Integer.valueOf(t);
}
}
``````

// Line 24: error: missing return statement

1. top is passed by value, we need pass-by-reference here.

2. t=='+' is wrong.

3. for return missing, use if and else-if

public class Solution {
class RefInt {
public int val = 0;
public RefInt(int val) {
this.val = val;
}
}

``````public int evalRPN(String[] tokens) {
return helper(tokens, new RefInt(tokens.length-1));
}

int helper(String[] tokens, RefInt top)
{
String t = tokens[top.val];
top.val--;
if(t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/"))
{
int n0 = helper(tokens, top);
int n1 = helper(tokens, top);
if (t.equals("+")) return n1+n0;
else if(t.equals("-")) return n1-n0;
else if(t.equals("*")) return n1*n0;
else return n1/n0;
}
else{
return Integer.valueOf(t);
}
}
``````

}

• Version 1.1

``````int evalRPN(vector<string>& tokens) {
string s = tokens.back(); tokens.pop_back();
if(s != "+" && s != "-" && s != "*" && s != "/") return stoi(s);

int r2 = evalRPN(tokens), r1 = evalRPN(tokens);

if(s == "+") return r1 + r2;
if(s == "-") return r1 - r2;
if(s == "*") return r1 * r2;
if(s == "/") return r1 / r2;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.