在 "Shunting Yard Algorithm" 中添加公式和变量支持的最佳方式是什么？

Question

我目前正在这个名为“表达式求值器”的项目中工作，我有一些关于如何编码的问题。

首先，这个“表达式求值器”是做什么的？它只是计算你插入的表达式，它必须支持：

圆括号
运算符：+、-、/、*、<>、=、<=、>=、or、and、xor、not、mod、\
here
实数、整数和逻辑常量（1、1.1、-1、true、false 等）
像var这样的普通变量，例如：1 + var //变量可以这样使用：“var = 50 1 + var”它应该输出51。

我目前设法将字符串转换为后缀表示法（反向波兰表示法）并对其求值，但它目前仅支持 (+, -, *, /, ^) 并且仅支持实数和整数常量。

如何添加对 operators/variables/formulas 其余部分的支持？

我实际上已经尝试添加对 variables/formulas 的支持，但它仅适用于基本表达式，例如：pow(1, 3) + 2，输出 3 (TRUE)。如果我尝试更复杂的表达式，它会发生类似于：pow(pow(2, 3), 2)，这输出 512，这是错误的，它应该输出 64.

Here's我的代码所以你可以自己测试。

#include <algorithm>
#include <cmath>
#include <fstream>
#include <map>
#include <stack>
#include <string>
#include <vector>

#include <iostream>

// Setari
#define __DEBUG__ // Afiseaza informatii despre procesul de rezolvare.
#define __SUPPORT_DOUBLE__ // Activeaza suportul pentru numere reale.

// Variabile

std::vector<std::string> Infix;
std::stack<std::string> operators;
std::stack<std::string> Rezultat;

// Salvez operatorii si nivelul lor de prioritate intr-un dictioar pentru a face procesul de identificare mai rapid
std::map<std::string, short> Operators = { {"+", 1}, {"-", 1}, {"*", 2}, {"/", 2}, {"^", 3}, {"pow", 3}, {"==", 4}, {"=", 5} };

std::ifstream fin("eval.in");
std::ofstream fout("eval.out");


// Functii

// Caut in dictionarul 'Operators' operatorul si, daca-l gasesc returnez prioritatea acestuia.
int CheckOperator(const std::string& op){
    const auto& it = Operators.find(op);

    if (it != Operators.end())
        return it->second;

    return 0;
}

int main(){
    std::string expr, token;
    while (std::getline(fin, token))
        expr.append(token);
    fin.close();
    
    // Analizez expresie si sterg caracterele inutile( \ ).
    expr.erase(std::remove_if(expr.begin(), expr.end(), [](const char& c){ return c == '\'; }), expr.end());
    // Transform expresia in expresie postfix.
    
    for (size_t i = 0; i < expr.length(); ++i){
        char c = expr[i];
        token.clear();

        int prioritate = 0;
        
        token += c;
        if (isdigit(c))
        {
            
            for (++i; i < expr.length(); ++i){
                c = expr[i];
#if defined(__SUPPORT_DOUBLE__)
                if (!isdigit(c) && c != '.')
                    break;
#else
                if (!isdigit(c))
                    break;
#endif
                token += c;
            }
            --i;
            Infix.push_back(token);
        }
        else if(isalpha(c))
        {
            for (++i; i < expr.length(); ++i){
                c = expr[i];

                if (!isalnum(c))
                    break;
                
                token += c;
            }
            std::cout << "Verificare: " << token << '\n';
            
            --i;

            if (CheckOperator(token))
                operators.push(token);
            else
                Infix.push_back(token);
        }
        else if((prioritate = CheckOperator(token))){
            bool numar = false;
            for (++i; i < expr.length(); ++i){
                c = expr[i];
                token += c;
#if defined(__SUPPORT_DOUBLE__)
                if (!CheckOperator(token) && !isdigit(c) && c != '.'){
                    token.erase(token.length() - 1, token.length());
                    break;
                }
#else
                if (!CheckOperator(token) && !isdigit(c)){
                    token.erase(token.length() - 1, token.length());
                    break;
                }
#endif
                if (isdigit(c))
                    numar = true;
            }
            --i;
            if (!numar){
                while(!operators.empty() && CheckOperator(operators.top()) >= prioritate)
                {
                    Infix.push_back(operators.top());
                    operators.pop();
                }
                operators.push(token);
            }
            else
            {
                Infix.push_back(token);
            }
            
        }
        else if (c == '(')
        {
            operators.push("(");
        }
        else if (c == ')')
        {
            while (!operators.empty())
            {
                if (operators.top() == "("){
                    operators.pop();
                    break;
                }
                Infix.push_back(operators.top());
                operators.pop();
            }
        }
    }
    while (!operators.empty())
    {
        Infix.push_back(operators.top());
        operators.pop();

    }

#if defined(__DEBUG__)
    for (const auto& ex : Infix)
        fout << ex << ' ';
    fout << '\n';
#endif

    auto& it = Infix.begin();
    for(; it != Infix.end(); ++it)
    {
        if (CheckOperator(*it))
        {
            if (*it == "+")
            {
                long double b = std::stold(Rezultat.top());
                Rezultat.pop();
                long double a = std::stold(Rezultat.top());
                Rezultat.pop();

                Rezultat.push(std::to_string(a + b));
            }
            else if(*it == "-")
            {
                long double b = std::stold(Rezultat.top());
                Rezultat.pop();
                long double a = std::stold(Rezultat.top());
                Rezultat.pop();

                Rezultat.push(std::to_string(a - b));
            }
            else if(*it == "*")
            {
                long double b = std::stold(Rezultat.top());
                Rezultat.pop();
                long double a = std::stold(Rezultat.top());
                Rezultat.pop();

                Rezultat.push(std::to_string(a * b));
            }
            else if(*it == "/")
            {
                long double b = std::stold(Rezultat.top());
                Rezultat.pop();
                long double a = std::stold(Rezultat.top());
                Rezultat.pop();

                Rezultat.push(std::to_string(a / b));
            }
            else if(*it == "^")
            {
                long double b = std::stold(Rezultat.top());
                Rezultat.pop();
                long double a = std::stold(Rezultat.top());
                Rezultat.pop();

                Rezultat.push(std::to_string(std::powl(a, b)));
            }
            else if(*it == "==")
            {
                long double b = std::stold(Rezultat.top());
                Rezultat.pop();
                long double a = std::stold(Rezultat.top());
                Rezultat.pop();

                Rezultat.push(std::to_string(a == b));
            }
            else if(*it == "pow")
            {
                long double b = std::stold(Rezultat.top());
                Rezultat.pop();
                long double a = std::stold(Rezultat.top());
                Rezultat.pop();

                Rezultat.push(std::to_string(std::powl(a, b)));
            }
        }
        else
        {
            Rezultat.push(*it);
        }
    }
#if defined(__SUPPORT_DOUBLE__)
    fout << Rezultat.top() << '\n';
#else
    fout << std::stol(Rezultat.top()) << '\n';
#endif
    return 0;
}

谢谢！

编辑：如果您需要，我已经在 Github 上发布了解决方案。

Answer 1

不太清楚你所说的“公式”是什么意思。

调车场算法中的变量与数字的行为方式完全相同，没有任何区别。

赋值 x = y 可以被视为另一种表达式。您想要将 = 运算符添加到支持的运算符列表中。只需选择其优先级即可。

显然，求值器需要将变量与常量和表达式区分开来，以便它可以在每种情况下发出错误信号：

    x + 2 (undefined x)
    2 = 5 (assignment to non-variable)
(1+2) = 3 (same)

请注意，您现在希望能够计算多个表达式，这样您就可以将 var = 50 和 1 + var 作为两个单独的表达式计算。设计一种方法将它们分开。 ; 字符可以很好地用于此目的。

另请注意，确实不建议让 = 同时用于比较和赋值。您想像现在大多数编程语言那样将比较更改为 ==，或者更改赋值以使用其他符号，例如 := 或 <-.

在 "Shunting Yard Algorithm" 中添加公式和变量支持的最佳方式是什么？

What is the best way to add formulas and variables support in "Shunting Yard Algorithm"?

c++

formula