运算表达式测试

#include <iostream>
#include <thread>
#include <set>
#include <map>
#include <string>
using namespace std;

typedef map<string, double> ValueMap;
//表达式树
class ExpressionNode
{
public:
    virtual double calculate(ValueMap vars) = 0;

};
//常数结点
class Constant :public ExpressionNode
{
public:
    double value;
    Constant(double value)
    {
        this->value = value;
    }
    double calculate(ValueMap vars)
    {
        return value;
    }
};

//未知数结点
class VariableReference :public ExpressionNode
{
public:
    string name;
    VariableReference(string name)
    {
        this->name = name;
    }
    double calculate(ValueMap vars)
    {
        double value = vars[name];
        return value;
    }
};
//运算结点
class Operation :public ExpressionNode
{
public:
    //左边的表达式
    ExpressionNode *left;
    //当前运算
    char op;
    //右边的表达式
    ExpressionNode *right;
    Operation(ExpressionNode *left, char op, ExpressionNode *right)
    {
        this->left = left;
        this->op = op;
        this->right = right;
    }
    //计算值
    double calculate(ValueMap vars)
    {
        //递归计算
        double x = left->calculate(vars);
        double y = right->calculate(vars);
        //运算
        switch (op)
        {
        case '+':return x + y;
        case '-':return x - y;
        case '*':return x*y;
        case '/':return x / y;
        }
    }
};
// 将字符串转换为树
// s起始位置，t结束位置
// variables 输出从表达式中提取出的未知数
ExpressionNode *strToTree(string str, int s, int t, set<string> &varibales)
{
    // 去除包含整个当前表达式的括号
    while (s <= t && str[s] == '(' && str[t] == ')')
        s++, t--;
    if (s > t)
        return new Constant(0);
    // findLetter找到字母，用以判断是否为未知数
    // findChar找到字符，用以判断是否存在运算符
    bool findLetter = false, findChar = false;
    // 括号标记
    int brackets = 0;
    // lastPS最后的加减法
    // lastMD最后的乘除
    int lastPS = -1, lastMD = -1;

    for (int i = s; i <= t; i++)
    {
        // 当前位置不是常数
        if (str[i] != '.' && (str[i] < '0' || str[i] > '9'))
        {
            // 如果是字母的话
            if ((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z'))
                findLetter = true;
            else
            {
                // 不是常数，不是字母，就是运算符
                findChar = true;
                switch (str[i])
                {
                case '(':
                    brackets++;
                    break;
                case ')':
                    brackets--;
                    break;
                    // 更新最后加减法的位置
                case '+':
                case '-':
                    if (!brackets)
                        lastPS = i;
                    break;
                    // 更新最后乘除法的位置
                case '*':
                case '/':
                    if (!brackets)
                        lastMD = i;
                    break;
                }
            }
        }
    }
    // 从s到t都是常数
    if (findLetter == false && findChar == false)
        return new Constant(stod(str.substr(s, t - s + 1)));
    // 从s到t是未知数
    if (findChar == false)
    {
        varibales.insert(str.substr(s, t - s + 1));
        return new VariableReference(str.substr(s, t - s + 1));
    }
    // 从s到t是个运算
    // 没有加减就用乘除
    if (lastPS == -1)
        lastPS = lastMD;
    return new Operation(strToTree(str, s, lastPS - 1, varibales), str[lastPS], strToTree(str, lastPS + 1, t, varibales));
}

void test()
{
    ValueMap vars;
    // 这里设置未知数
    vars["a"] = 123;
    vars["b"] = 100;
    // 输入字符串
    string str;
    cin >> str;
    // 转换为树
    set<string> variables;
    ExpressionNode *tree = strToTree(str, 0, str.length() - 1, variables);
    // 输出值
    cout << tree->calculate(vars) << endl;
    return;
}

double testCal(double a, double b)
{
    return a+b*a/(b-5);
}

#define MAXCOUNT 1000 * 1000
int main()
{
    //模拟栅格值
    //栅格a
    double *rasterA = (double*)malloc(sizeof(double) * MAXCOUNT);
    //栅格b
    double *rasterB = (double*)malloc(sizeof(double) * MAXCOUNT);
    for(int i = 0; i < MAXCOUNT; i++)
    {
        rasterA[i] = rand();
        rasterB[i] = rand();
    }

    //输入栅格计算表达式
    string str = "rasterA+rasterB*rasterA/(rasterB-5)";
    //转换为树
    set<string> variableSet;
    ExpressionNode *tree = strToTree(str, 0, str.length() - 1, variableSet);

    // 使用树运算
    auto start1 = std::chrono::high_resolution_clock::now();
    for(int i = 0; i < MAXCOUNT; i++)
    {
        ValueMap vars;
        for(string v : variableSet)
        {
            if(v == "rasterA")
            {
                vars[v] = rasterA[i];
            }
            else if(v == "rasterB")
            {
                vars[v] = rasterB[i];
            }
        }
        tree->calculate(vars);
    }
    auto end1= std::chrono::high_resolution_clock::now();
    auto delta1 = std::chrono::duration_cast<std::chrono::milliseconds>(end1-start1);
    std::cout << "delta1:"<<delta1.count()<<endl;

    // 使用函数运算
    auto start2 = std::chrono::high_resolution_clock::now();
    for(int i = 0; i < MAXCOUNT; i++)
    {
        ValueMap vars;
        for(string v : variableSet)
        {
            if(v == "rasterA")
            {
                vars[v] = rasterA[i];
            }
            else if(v == "rasterB")
            {
                vars[v] = rasterB[i];
            }
        }
        testCal(rasterA[i], rasterB[i]);
    }
    auto end2= std::chrono::high_resolution_clock::now();
    auto delta2 = std::chrono::duration_cast<std::chrono::milliseconds>(end2-start2);
    std::cout << "delta2:"<<delta2.count()<<endl;
    free(rasterA);
    free(rasterB);
    return 0;
}