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


  • 24
    Y

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


  • 1
    H

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


  • 0
    H

    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


  • 0
    J
    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);
        }
    }
    

    }


  • 0
    H

    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;
        }

Log in to reply
 

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