How do I represent algebraic terms in C++ using classes: a term can be raised to a vector of terms

Question

I'm trying to make an algebraic parser, and I've gotten decently far. I'm at the point where I can successfully multiply polynomials.

Full code here. Use the constructors along with the '*' overload and convert the resulting algexpr object to a string using .latex() to multiply and print to stdout. It's alpha at best, and I know there are many optimizations I need to make, I also still need to implement division, but that's not what my question is about.

x^2 is as algebraic term. So it 3ax, 7x^2(sin(x))zx, sin(a+b), and x^(2n+1). I'm having problems with the ones I have made bold. Both of these involve algebraic expressions, even though they are algebraic terms, but an algebraic expression is a vector of algebraic terms. So in order to completely represent an algebraic term, I need an algebraic expression, but an algebraic expression is a vector of algebraic terms. You can start to see my issue. I want to be able to use algebraic expressions inside algebraic terms.

The program doesn't work with the terms in bold, nor any expressions involving them. It enters an infinite loop instead, which is understandable since I haven't been able to figure out how I'd implement this yet.

Here's a minimal reproducible example to illustrate my troubles. This is what I want to do, however, this won't work.

code.cpp:8:3: error: ‘algexpr’ does not name a type
    8 |   algexpr power; // I can't use algexpr here because it's not defined yet.

code.cpp:

class variable {
public:
  std::string name;
  algexpr power; // I can't use algexpr here because it's not defined yet.

  variable(std::string str) {
    // fancy parsing code here
    if (str == "x") {
      name = "x";
      power = algexpr("1");
    }
  }
};

class algterm {
public:
  rfraction constant;
  std::vector<variable> variables;

  algterm(std::string str) {
    // fancy parsing code here
    if (str == "parse") {
      constant = rfraction("1");
      variables.push_back(variable("x"));
    }
  }
};

class algexpr {
public:
  std::vector<algterm> terms;

  algexpr(std::string str) {
    // fancy parsing code here
    terms.push_back(algterm("parse"));
  }
};

I've tried thinking about what to do, but couldn't come up with anything that great. One idea was to store everything as strings (the expressions, variables, and terms) and just re-parse it every single time, but that's clearly not that efficient. How do I solve this?

Answer 1

Maybe you can use a parse tree design like this:

#include <cmath>
#include <string>

struct Expression {
    virtual ~Expression() = default;

    virtual double eval() const = 0; 
};

struct Variable: Expression {
    double eval() const override { 
        // Store a map of all your variable names somewhere and look it up
    }

    std::string name;
};

struct BinaryExpression: Expression {
    enum Operator { Plus, Minus, Times, Divide, Power };

    double eval() const override {
        switch (op) {
        case Plus: return lhs->eval() + rhs->eval();
        case Minus: return lhs->eval() - rhs->eval();
        // Other operators here...
        }
    }

    std::unique_ptr<Expression> lhs, rhs;
    Operator op;
};

struct FunctionCall: Expression {
    double eval() const override {
        if (functionName == "sin") { 
            return std::sin(argument->eval());
        }
        if (functionName == "cos") { /* ... */ }
        // and so on... 
    }

    std::string functionName; // E.g. "sin", "cos", etc.
    std::unique_ptr<Expression> argument;
    // ^^^ Make this a vector of unique_ptr's if you want to 
    //     have functions with more than one argument. 
};

Then e.g. your algexpr class would become a chain of BinaryExpression's with Operator::Plus. You can express exponentiation of a variable with the BinaryExpression class and Operator::Power. This way you can represent arbitrary expressions raised to the power of any other arbitrary expression.

This way you also don't really need the forward declarations because everything is implemented in terms of the Expression base class which is defined first.

This is perhaps a bit more general than you would need for only representing polynomials, but as you also want to support sin and cos functions and raising expressions to the power of other general expressions you will probably need a design like this.

Edit:

To clarify, then a + b + c would be represented like this:

                        BinaryExpression(Plus)
                          /              \
         BinaryExpression(Plus)       Variable("c")
           /          \
Variable("a")      Variable("b")
       

sin(a + b) like this:

         FunctionCall("sin")
                |
       BinaryExpression(Plus)  
           /          \
Variable("a")      Variable("b")

and x^(2n + 1) like this:

       BinaryExpression(Power)
          /              \
  Variable("x")       BinaryExpression(Plus)
                          /           \
          BinaryExpression(Times)   Constant(1)
             /              \
      Constant(2)       Variable("n")

The last example requires another class Constant to be added to the parse tree. Also it's probably a good idea to differentiate between variables and parameters, which I didn't do here.