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

As a reference. This solution in C# works. Are they checking some boundary that I am not? https://github.com/rogerchang1/codeeval/blob/master/PrefixExpression.cs — Anton Savelyev, Oct 27 '15 at 10:00
One problem is that you should not use `while (!file.eof())`, see ["Why is “while ( !feof (file) )” always wrong?"](http://stackoverflow.com/questions/5431941/why-is-while-feof-file-always-wrong). — Some programmer dude, Oct 27 '15 at 10:01
Also, if you want to separate tokens on whitespace only, a `std::ostringstream` and the normal output operator `>>` should work as well. Or just using `std::copy` with `std::ostream_iterator` and `std::back_inserter`. — Some programmer dude, Oct 27 '15 at 10:05
@JoachimPileborg Fixed it. Changed it to while(getline(file, line)) — Anton Savelyev, Oct 27 '15 at 10:08
With the change to the while loop (accessing the file), I was able to improve my score to 97.5. — Anton Savelyev, Oct 27 '15 at 10:09
So it just doesn't work on one test case. @JoachimPileborg could you show me how the tokenize function would look with the >> operator? — Anton Savelyev, Oct 27 '15 at 10:16
It's slightly unclear what the challenge means with "separated by a whitespace" ("whitespace" isn't a countable noun). Perhaps there could be tab characters, or multiple space characters. — molbdnilo, Oct 27 '15 at 10:25
@Eidbanger `tokenize`, short version: `std::istringstream stream(str); std::string token; while (stream >> token) { tokens.push_back(token); }`. — molbdnilo, Oct 27 '15 at 10:28
@molbdnilo Thanks. I chose to do this `copy(istream_iterator(iss), istream_iterator(), back_inserter(tokens));` But then it took to long to compile on their website.... — Anton Savelyev, Oct 27 '15 at 10:29
@molbdnilo so then I tried your version.. Same thing.. Wont even compile through their website... — Anton Savelyev, Oct 27 '15 at 10:39

score 1 · Accepted Answer · answered Oct 27 '15 at 11:13

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

Prefix Expression Evaluation in C++ [CodeEval]

1 Answers1