c++ - C++ 中的前缀表达式求值 [CodeEval]

Question

Here是挑战的链接。这是为了您的方便:

前缀表达式描述:您将获得一个前缀表达式。编写程序对其进行评估。输入样本:第一个参数将是一个输入文件，每行有一个前缀表达式。例如* + 2 3 4您的程序必须读取它并将其插入到您喜欢的任何数据结构中。遍历该数据结构并评估前缀表达式。每个 token 是由空格分隔。您可能会假设出现的唯一有效运算符在测试数据中是'+'，'*'和'/'输出样本:打印到标准输出，前缀表达式的输出，每行一个。例如20"

我的代码有时会被 CodeEval 拒绝，因为编译时间超过 10 秒。当它编译时，我得到了 85/100 的分数，因为我认为在 40 个测试用例中，我得到了一些不正确的分数。我相信我的算法是正确的，问题只在于检查边界/极端情况。谁能帮我优化这段代码以在 CodeEval 中工作？

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

这里是最新的代码(能编译一次的97.5分):

    #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

完成了。他们想要 float 值(value)。谢谢。

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