c++ - C++中的前缀表达评估[CodeEval]

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

最佳答案

完成。他们想要 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;
    }