Prefix Expression Evaluation in C++ [CodeEval]

Question

Here is a link to the challenge. Here it is for your convenience:

Prefix Expressions Description: You are given a prefix expression. Write a program to evaluate it. Input sample: The first argument will be an input file with one prefix expression per line. e.g. * + 2 3 4 Your program has to read this and insert it into any data structure you like. Traverse that data structure and evaluate the prefix expression. Each token is delimited by a whitespace. You may assume that the only valid operators appearing in test data are '+','*' and '/' Output sample: Print to stdout, the output of the prefix expression, one per line. e.g. 20"

My code that sometimes gets rejected by CodeEval because it takes longer than 10 seconds to compile. And when it does compile, I get a score of 85/100 because I think that out of the 40 test cases, I get some incorrect. I believe that my algorithm is correct and the issue is only in checking the boundary/extreme cases. Can anyone help me optimize this code to work in CodeEval please?

    #include <iostream>
    #include <fstream>
    #include <cstdlib>
    #include <vector>
    #include <string>

    using namespace std;

    void tokenize(string& str, vector<string>& tokens)
    {
        int pos;
        string token;
        while ((pos = str.find(" ")) != std::string::npos )
        {
            token = str.substr(0,pos);
            tokens.push_back(token); 
            str.erase(0, pos + 1);  
        }
        tokens.push_back(str.c_str());  
    }

    bool isOperator(string str)
    {
        if((str == "+") || (str == "-") || (str == "*") || (str == "/") )
            return true;
        else
            return false;
    }

    int compute(string oper, int val1, int val2)
    {
        if(oper == "+")
            return (val1 + val2);
        else if(oper == "*")
            return (val1 * val2);
        else if(oper == "/")
            return (val1 / val2); 
        else if(oper == "-")
            return (val1 - val2);
    }

    void evalPrefix(vector<string>& expression)
    {
        vector<int> numStack;
        int num1;
        int num2;

        for (int i = (expression.size() - 1); i >=0; i--)
        {
            if(isOperator(expression[i]))
            {
                num1 = numStack.back();
                numStack.pop_back();
                num2 = numStack.back();
                numStack.pop_back();
                numStack.push_back(compute(expression[i], num1, num2));
            }
            else
            {
                numStack.push_back(atoi(expression[i].c_str()));
            }
        }
        cout << numStack[0] << endl;
    }



    int main(int argc, char *argv[]) 
    {
        ifstream file(argv[1]);
        string line;
        string token; 
        vector<string> tokens; 

        while (!file.eof()) //processing the file
        {
            getline(file, line);
            if(line.length() == 0)
                continue;
            else
            {
                tokens.clear();
                tokenize(line, tokens); //tokenizing the file
                if(tokens.size())
                    evalPrefix(tokens);
            }
        }
        return 0;
    } 

Here is the most updated code (97.5 score that was able to compile once):

    #include <iostream>
    #include <fstream>
    #include <cstdlib>
    #include <vector>
    #include <string>

    using namespace std;

    void tokenize(string& str, vector<string>& tokens)
    {
        int pos;
        string token;
        while ((pos = str.find(" ")) != std::string::npos )
        {
            token = str.substr(0,pos);
            tokens.push_back(token); 
            str.erase(0, pos + 1);  
        }
        tokens.push_back(str.c_str());  
    }

    bool isOperator(string str)
    {
        if((str == "+") || (str == "*") || (str == "/") )
            return true;
        else
            return false;
    }

    int compute(string oper, int val1, int val2)
    {
        if(oper == "+")
            return (val1 + val2);
        else if(oper == "*")
            return (val1 * val2);
        else if(oper == "/")
            return (val1 / val2); 
        else
            return 0;
    }

    void evalPrefix(vector<string>& expression)
    {
        vector<int> numStack;
        int num1;
        int num2;

        for (int i = (expression.size() - 1); i >=0; i--)
        {
            if(isOperator(expression[i]))
            {
                num1 = numStack.back();
                numStack.pop_back();
                num2 = numStack.back();
                numStack.pop_back();
                numStack.push_back(compute(expression[i], num1, num2));
            }
            else
            {
                numStack.push_back(atoi(expression[i].c_str()));
            }
        }
        cout << numStack[0] << endl;
    }



    int main(int argc, char *argv[]) 
    {
        ifstream file(argv[1]);
        string line;
        string token; 
        vector<string> tokens; 

        while (getline(file, line)) //processing the file
        {
            if(line.length() == 0)
                continue;
            else
            {
                tokens.clear();
                tokenize(line, tokens); //tokenizing the file
                if(tokens.size())
                    evalPrefix(tokens);
            }
        }
        return 0;
    } 

Answer 1

It's done. They wanted floating values. Thanks.

    #include <iostream>
    #include <fstream>
    #include <cstdlib>
    #include <vector>
    #include <string>

    using namespace std;

    void tokenize(string& str, vector<string>& tokens)
    {
        int pos;
        string token;
        while ((pos = str.find(" ")) != std::string::npos )
        {
            token = str.substr(0,pos);
            tokens.push_back(token); 
            str.erase(0, pos + 1);  
        }       
        tokens.push_back(str.c_str());  
    }

    bool isOperator(string str)
    {
        if((str == "+") || (str == "*") || (str == "/") )
            return true;
        else
            return false;
    }

    float compute(string oper, float val1, float val2)
    {
        if(oper == "+")
            return (val1 + val2);
        else if(oper == "*")
            return (val1 * val2);
        else if(oper == "/")
            return (val1 / val2); 
        else
            return 0;
    }

    void evalPrefix(vector<string>& expression)
    {
        vector<float> numStack;
        float num1;
        float num2;

        for (int i = (expression.size() - 1); i >=0; i--)
        {
            if(isOperator(expression[i]))
            {
                num1 = numStack.back();
                numStack.pop_back();
                num2 = numStack.back();
                numStack.pop_back();
                numStack.push_back(compute(expression[i], num1, num2));
            }
            else
            {
                numStack.push_back(atoi(expression[i].c_str()));
            }
        }
        int i = int (numStack[0] + 0.5);
        cout << i << endl;
    }



    int main(int argc, char *argv[]) 
    {
        ifstream file(argv[1]);
        string line;
        string token; 
        vector<string> tokens; 

        while (getline(file, line)) //processing the file
        {
            if(line.length() == 0)
                continue;
            else
            {
                tokens.clear();
                tokenize(line, tokens); //tokenizing the file
                if(tokens.size())
                    evalPrefix(tokens);
            }
        }
        return 0;
    }