c++ - 后缀评估很慢-优化？

标签 c++ postfix-notation

我写了一个小的表达式计算器。首先，表达式被分解为后缀符号。让我们使用以下示例:

中缀 = "z*z+c"

我的代码创建了以下形式的字符串 vector :z, z, *, c, +

这个问题不是调车场本身的问题，而是评估这个postfix的东西。我创建了另一个函数:

Complex Evaluate(vector<string> post, Complex z, Complex c)
{
    vector<Complex> stack;
    Complex a1, a2, a3;
    for (int i = 0; i < post.size(); i++)
    {
        string s = post[i];
        if (IsNumber(s))
        {
            stack.push_back(stold(s));
        }
        else if (IsConst(s))
        {
            if (s == "pi")
            {
                stack.push_back(Pi);
            }
            else if (s == "e")
            {
                stack.push_back(E);
            }
            else if (s == "phi")
            {
                stack.push_back(2.61803398875);
            }
            else if (s == "eulergamma")
            {
                stack.push_back(EulerGamma);
            }
            else if (s == "i")
            {
                stack.push_back(I);
            }
        }
        else if (IsOperator(s))
        {
            if (s == "+")
            {
                a1 = stack[stack.size() - 1];
                a2 = stack[stack.size() - 2];
                stack.pop_back(); stack.pop_back();
                stack.push_back(a1 + a2);
            }
            else if (s == "-")
            {
                a1 = stack[stack.size() - 1];
                a2 = stack[stack.size() - 2];
                stack.pop_back(); stack.pop_back();
                stack.push_back(a2 - a1);
            }
            else if (s == "*")
            {
                a1 = stack[stack.size() - 1];
                a2 = stack[stack.size() - 2];
                stack.pop_back(); stack.pop_back();
                stack.push_back(a1 * a2);
            }
            else if (s == "/")
            {
                a1 = stack[stack.size() - 1];
                a2 = stack[stack.size() - 2];
                stack.pop_back(); stack.pop_back();
                stack.push_back(a2 / a1);
            }
            else if (s == "^")
            {
                a1 = stack[stack.size() - 1];
                a2 = stack[stack.size() - 2];
                stack.pop_back(); stack.pop_back();
                stack.push_back(pow(a2, a1));
            }
        }
        else if (IsFunction(s))
        {
            if (s == "sqrt")
            {
                stack[stack.size() - 1] = sqrt(stack[stack.size() - 1]);
            }
            else if (s == "sin")
            {
                stack[stack.size() - 1] = sin(stack[stack.size() - 1]);
            }
            else if (s == "arcsin" || s == "asin")
            {
                stack[stack.size() - 1] = asin(stack[stack.size() - 1]);
            }
            else if (s == "sinc")
            {
                stack[stack.size() - 1] = sinc(stack[stack.size() - 1]);
            }
            else if (s == "cos")
            {
                stack[stack.size() - 1] = cos(stack[stack.size() - 1]);
            }
            else if (s == "cosc")
            {
                stack[stack.size() - 1] = cosc(stack[stack.size() - 1]);
            }
            else if (s == "arccos" || s == "acos")
            {
                stack[stack.size() - 1] = acos(stack[stack.size() - 1]);
            }
            else if (s == "tan" || s == "tg")
            {
                stack[stack.size() - 1] = tan(stack[stack.size() - 1]);
            }
            else if (s == "arctan" || s == "atan")
            {
                stack[stack.size() - 1] = atan(stack[stack.size() - 1]);
            }
            else if (s == "cot" || s == "cotg" || s == "cotan")
            {
                stack[stack.size() - 1] = cot(stack[stack.size() - 1]);
            }
            else if (s == "exp")
            {
                stack[stack.size() - 1] = exp(stack[stack.size() - 1]);
            }
            else if (s == "log" || s == "ln" || s == "lg")
            {
                stack[stack.size() - 1] = log(stack[stack.size() - 1]);
            }
            else if (s == "log10")
            {
                stack[stack.size() - 1] = log(stack[stack.size() - 1]) / Complex(log(10), 0);
            }
            else if (s == "log2")
            {
                stack[stack.size() - 1] = log(stack[stack.size() - 1]) / Complex(log(2), 0);
            }
            else if (s == "sinh" || s == "sh")
            {
                stack[stack.size() - 1] = sinh(stack[stack.size() - 1]);
            }
            else if (s == "arcsinh" || s == "asinh" || s == "ash")
            {
                stack[stack.size() - 1] = arcsinh(stack[stack.size() - 1]);
            }
            else if (s == "cosh" || s == "ch")
            {
                stack[stack.size() - 1] = cosh(stack[stack.size() - 1]);
            }
            else if (s == "arccosh" || s == "acosh" || s == "ach")
            {
                stack[stack.size() - 1] = arccosh(stack[stack.size() - 1]);
            }
            else if (s == "tanh" || s == "th" || s == "tgh")
            {
                stack[stack.size() - 1] = tanh(stack[stack.size() - 1]);
            }
            else if (s == "arctanh" || s == "atanh" || s == "ath")
            {
                stack[stack.size() - 1] = arctanh(stack[stack.size() - 1]);
            }
            else if (s == "cotanh" || s == "coth" || s == "ctgh" || s == "cth")
            {
                stack[stack.size() - 1] = coth(stack[stack.size() - 1]);
            }
            else if (s == "arccoth" || s == "acoth" || s == "acth")
            {
                stack[stack.size() - 1] = arccoth(stack[stack.size() - 1]);
            }
            else if (s == "lgamma" || s == "loggamma" || s == "logamma")
            {
                stack[stack.size() - 1] = lgamma(stack[stack.size() - 1], max(100000, (int)round(100000 * (abs(stack[stack.size() - 1]).Re))));
            }
        }
        else if (IsParam(s))
        {
            if (s == "z") { stack.push_back(z); }
            else if (s == "c") { stack.push_back(c); }
        }
    }
    return stack[stack.size() - 1];
}

因此，如果我调用 Evaluate (postfix, 4, 2)，我会得到正确的 4*4+2 = 18。但是，我需要遍历许多复杂的点(第三个参数，c)，所以我需要非常执行这个迅速地。当我执行以下操作(测试速度)时:

for (int i = 0; i < 500000; i++)
{
    if ((i % 1000) == 0) { cout << i << endl; }
    result = Evaluate(postfix, 4, 2);
}

需要几十秒才能完成，非常非常慢。快速执行后缀表达式求值的典型方法是什么？为了完整起见，我还包括了 Complex.h 和 Complex.cpp:

#pragma once
#ifndef COMPLEX_H
#define COMPLEX_H

class Complex
{
public:
    long double Re, Im;
    Complex(long double re = 0., long double im = 0.);
    friend Complex operator+(Complex, Complex);
    friend Complex operator+(long double, Complex);
    friend Complex operator+(Complex, long double);
    friend Complex operator-(Complex, Complex);
    friend Complex operator-(long double, Complex);
    friend Complex operator-(Complex, long double);
    Complex operator-() const &;
    friend Complex operator*(Complex, Complex);
    friend Complex operator*(long double, Complex);
    friend Complex operator*(Complex, long double);
    friend Complex operator/(Complex, Complex);
    friend Complex operator/(long double, Complex);
    friend Complex operator/(Complex, long double);
};

Complex operator+ (Complex c1, Complex c2);
Complex operator+ (long double r, Complex c);
Complex operator+ (Complex c, long double r);
Complex operator- (Complex c1, Complex c2);
Complex operator- (long double r, Complex c);
Complex operator- (Complex c, long double r);
Complex operator* (Complex c1, Complex c2);
Complex operator* (long double r, Complex c);
Complex operator* (Complex c, long double r);
Complex operator/ (Complex c1, Complex c2);
Complex operator/ (long double r, Complex c);
Complex operator/ (Complex c, long double r);

Complex arg(Complex c);
Complex abs(Complex c);
Complex sqrt(Complex c);
Complex re(Complex c);
Complex im(Complex c);
Complex cc(Complex c);
Complex exp(Complex c);
Complex log(Complex c);
Complex sinh(Complex c);
Complex arcsinh(Complex c);
Complex cosh(Complex c);
Complex arccosh(Complex c);
Complex tanh(Complex c);
Complex arctanh(Complex c);
Complex coth(Complex c);
Complex arccoth(Complex c);
Complex pow(Complex c, int n);
Complex pow(Complex c1, Complex c2);
Complex sin(Complex c);
Complex asin(Complex c);
Complex sinc(Complex c);
Complex cos(Complex c);
Complex acos(Complex c);
Complex cosc(Complex c);
Complex tan(Complex c);
Complex atan(Complex c);
Complex cot(Complex c);
Complex acot(Complex c);
Complex lgamma(Complex c, int n);

#endif

#include "stdafx.h"
#include "stdio.h"
#include <iostream>
#include "Complex.h"

const long double EulerGamma = 0.57721566490153286060651209008240243104215933593992;
const Complex I = Complex(0, 1);

Complex::Complex(long double r, long double i)
{
    Re = r; Im = i;
}

Complex operator+ (Complex c1, Complex c2)
{
    return Complex(c1.Re + c2.Re, c1.Im + c2.Im);
}

Complex operator+ (long double r, Complex c)
{
    return Complex(r + c.Re, c.Im);
}

Complex operator+ (Complex c, long double r)
{
    return Complex(r + c.Re, c.Im);
}

Complex operator- (Complex c1, Complex c2)
{
    return Complex(c1.Re - c2.Re, c1.Im - c2.Im);
}

Complex operator- (long double r, Complex c)
{
    return Complex(r - c.Re, -c.Im);
}

Complex Complex::operator-() const &
{
    return Complex(- this->Re, - this->Im);
}

Complex operator- (Complex c, long double r)
{
    return Complex(c.Re - r, c.Im);
}

Complex operator* (Complex c1, Complex c2)
{
    Complex result;
    result.Re = (c1.Re * c2.Re - c1.Im * c2.Im);
    result.Im = (c1.Re * c2.Im + c1.Im * c2.Re);
    return result;
}

Complex operator* (long double r, Complex c)
{
    return Complex(r*c.Re, r*c.Im);
}

Complex operator* (Complex c, long double r)
{
    return Complex(r*c.Re, r*c.Im);
}

Complex operator/ (Complex c1, Complex c2)
{
    Complex result;
    result.Re = ((c1.Re * c2.Re + c1.Im * c2.Im) / (c2.Re*c2.Re + c2.Im*c2.Im));
    result.Im = ((c1.Im * c2.Re - c1.Re * c2.Im) / (c2.Re*c2.Re + c2.Im*c2.Im));
    return result;
}

Complex operator/ (long double r, Complex c)
{
    Complex result;
    result.Re = (r * c.Re / (c.Re*c.Re + c.Im*c.Im));
    result.Im = (-r * c.Im / (c.Re*c.Re + c.Im*c.Im));
    return result;
}

Complex operator/ (Complex c, long double r)
{
    return Complex(c.Re / r, c.Im / r);
}

Complex abs(Complex c)
{
    return Complex(sqrt(c.Re*c.Re + c.Im*c.Im), 0);
}

Complex arg(Complex c)
{
    return Complex(atan2(c.Im, c.Re), 0);
}

Complex sqrt(Complex c)
{
    long double r = abs(c).Re;
    long double phi = arg(c).Re;
    return Complex(sqrt(r)*cos(0.5*phi), sqrt(r)*sin(0.5*phi));
}

Complex re(Complex c)
{
    return Complex(c.Re, 0);
}

Complex im(Complex c)
{
    return Complex(0, c.Im);
}

Complex cc(Complex c)
{
    return Complex(c.Re, -c.Im);
}

Complex exp(Complex c)
{
    long double ex = exp(c.Re);
    return ex * Complex(cos(c.Im), sin(c.Im));
}

Complex log(Complex c)
{
    long double r = abs(c).Re;
    long double phi = atan2(c.Im, c.Re);
    return Complex(log(r), phi);
}

Complex sinh(Complex c)
{
    return Complex(sinh(c.Re)*cos(c.Im), cosh(c.Re)*sin(c.Im));
}

Complex arcsinh(Complex c)
{
    return log(c + sqrt(1 + c*c));
}

Complex cosh(Complex c)
{
    return Complex(cosh(c.Re)*cos(c.Im), sinh(c.Re)*sin(c.Im));
}

Complex arccosh(Complex c)
{
    return log(c + sqrt(c + 1)*sqrt(c - 1));
}

Complex tanh(Complex c)
{
    return sinh(c) / cosh(c);
}

Complex arctanh(Complex c)
{
    return 0.5*(log(1.0 + c) - log(1.0 - c));
}

Complex coth(Complex c)
{
    return cosh(c) / sinh(c);
}

Complex arccoth(Complex c)
{
    return 0.5*(log(1 + 1 / c) - log(1 - 1 / c));
}

Complex pow(Complex c, int n)
{
    if (n == 0)
    {
        return Complex(1, 0);
    }
    else if (n == 1)
    {
        return c;
    }
    else if (n > 0)
    {
        return c*pow(c, n - 1);
    }
    else
    {
        return Complex(1, 0) / pow(c, -n);
    }
}

Complex pow(Complex c1, Complex c2)
{
    if (abs(c2.Re - round(c2.Re)) > 1e-12 || c2.Im != 0)
    {
        return exp(c2*log(c1));
    }
    else
    {
        int n = round(c2.Re);
        return pow(c1, n);
    }
}

Complex sin(Complex c)
{
    return Complex(sin(c.Re)*cosh(c.Im), cos(c.Re)*sinh(c.Im));
}

Complex asin(Complex c)
{
    return -I*log(I*c + sqrt(abs(1 - c*c)) * exp(0.5*I*arg(1 - c*c)));
}

Complex sinc(Complex c)
{
    if (abs(c).Re > 0.01) { return sin(c) / c; }
    else { return 1 - c*c / 6 + c*c*c*c / 120; }
}

Complex cos(Complex c)
{
    return Complex(cos(c.Re)*cosh(c.Im), -sin(c.Re)*sinh(c.Im));
}

Complex acos(Complex c)
{
    return -I*log(c + I*sqrt(abs(1 - c*c)) * exp(0.5*I*arg(1 - c*c)));
}

Complex cosc(Complex c)
{
    if (abs(c).Re > 0.01) { return (1 - cos(c)) / c; }
    else { return c / 2 - c*c*c / 24 + c*c*c*c*c / 720; }
}

Complex tan(Complex c)
{
    return sin(c) / cos(c);
}

Complex atan(Complex c)
{
    return (1 / (2 * I))*log((I - c) / (I + c));
}

Complex cot(Complex c)
{
    return cos(c) / sin(c);
}

Complex acot(Complex c)
{
    return (1 / (2*I))*log((c + I) / (c - I));
}

Complex lgamma(Complex c, int n)
{
    Complex res = 0;
    res = -EulerGamma*c - log(c);
    for (int i = 1; i <= n; i++)
    {
        res = res + c / i - log(1 + c / i);
    }
    return res;
}

像 IsOperator 这样的附加函数是:

const vector<string> delimiters = { "(", ")", "[", "]", "{", "}" };
const vector<string> operators = { "+", "-", "/", "*", "^", "%" };
const vector<string> separators = { ",", ";", ":" };
const vector<string> params = { "x", "y", "z", "a", "b", "c", "w" };
const vector<string> constants = { "pi", "e", "eulergamma", "phi", "i" };
const Complex I = Complex(0, 1);
const long double EulerGamma = 0.57721566490153286060651209008240243104215933593992;
const long double Pi = 3.14159265358979323846264338327950288419716939937510;
const long double E = 2.71828182845904523536028747135266249775724709369995;

bool IsOperator(string isop)
{
    if (find(operators.begin(), operators.end(), isop) != operators.end())
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool IsParam(string ispar)
{
    if (find(params.begin(), params.end(), ispar) != params.end())
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool IsDelim(string isdel)
{
    if (find(delimiters.begin(), delimiters.end(), isdel) != delimiters.end())
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool IsConst(string iscon)
{
    if (find(constants.begin(), constants.end(), iscon) != constants.end())
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool IsSeparator(string issep)
{
    if (find(separators.begin(), separators.end(), issep) != separators.end())
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool LeftPar(string isleftpar)
{
    if (isleftpar == "(" || isleftpar == "[" || isleftpar == "{") { return true; }
    else { return false; }
}

bool RightPar(string isrightpar)
{
    if (isrightpar == ")" || isrightpar == "]" || isrightpar == "}") { return true; }
    else { return false; }
}

bool IsFunction(string isfun)
{
    if (!IsNumber(isfun) && !IsParam(isfun) && !IsConst(isfun) && !IsDelim(isfun) && !IsSeparator(isfun) && !IsOperator(isfun))
    {
        return true;
    }
    else
    {
        return false;
    }
}

基本上，我的问题是:为什么要花这么长时间？瓶颈在哪里？除了一堆 if else(代码必须以某种方式识别数字、变量、函数等)之外，它还能如何实现？我不需要你运行这段代码，我只希望有人看一下它并指出可以做得更好的地方(除了为这类事情导入外部库之外)。谢谢。

P.S.:我想使用 sin、cos、exp、pow 等函数，所以我必须拥有包含大量函数的第二部分。但据我所知，if else (IsFunction) 如果事先发现它是 z、c 或数字，则不会执行。

最佳答案

调用 IsOperator 然后依次与每个运算符进行比较是没有意义的。问题是目前，您正在进行大量 的字符串比较。为每个函数、常量和运算符创建一堆函数。有一个从字符串映射到适当函数的 std::unordered_map。在映射中查找函数，然后调用该函数。

类似于:

typedef void (*function)(std::stack<Complex>& stack, const Complex& z,
                                                     const Complex& c);

void plus(std::stack<Complex>& stack, const Complex& , const Complex& )
{
    const auto a1 = stack.top();
    stack.pop();
    const auto a2 = stack.top();
    stack.pop();
    stack.push( a1+a2 );
}

const static std::unordered_map<std::string, function> lookup_table
    { {"+",plus}, ... };

Complex Evaluate(const std::vector<string>& post, const Complex& z,
                                                  const Complex& c)
{
    std::stack<Complex> stack;
    for (const auto& s : post)
    {
        const auto it = lookup_table.find(s);
        if (it != lookup_table.end())
        {
            (it->second)(stack, z, c);
        }
        else if (IsNumber(s))
        {
            stack.push_back(stold(s));
        }
        else
        {
            // bad input
        }
     }
     ....

您可以通过创建一个包含堆栈和参数的 Evaluator 类，然后使函数成为该类的成员函数，来使它更流畅。然后你的映射将是“指向成员函数的指针”，你将调用 (evaluator->*(it-second))()。

请注意，我还切换到使用 std::stack，并通过引用传递所有内容。这对 post 参数特别有帮助。

关于c++ - 后缀评估很慢-优化？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46787306/

上一篇：c++ - 调用 std::vector<Class type> 的析构函数使 for_each 无效

下一篇：c++ - 前向引用混淆

相关文章：

java - 将表达式从前缀转换为后缀(面临优先问题)

c++ - 查找后缀到前缀表达式

c++ - 计算具有两个以上操作数的后缀表达式的问题

C++ 表达式 - 两者中哪一个更快？

c++ - 从模板分配空指针

c++ - 新行转义序列返回到行首

c - 以 float 和 int 表示形式计算 c 中表达式的不同值？

c# - C++ 转换为 C#

c++ - 多进程打开同一个文件导致文件操作失败

c - 在更新顶级变量时使用堆栈错误中缀到后缀

©2024 IT工具网  联系我们