Variable Operand and Logical Operator

#cpp #learning

The last two things that we will do are a method to resolve variable value, and support logical expressions by adding a production rule to parse an input string, and operators and, or.

Resolve variable value

To resolve a variable value, we can do so by passing a pointer to a function to a variable-operator node.

// dtype.h
...
class DTypeVar: public DType {
private:
    std::string name;
public:
    DTypeVar(const char *name, DType *(*get_val)(const char *name)=nullptr);
    DType* (*get_val)(const char *name);
    virtual void set_get_val(DType *(*get_val)(const char *name));
    ...
};

// dtype.cpp
void DTypeVar::set_get_val(DType *(*get_val)(const char *name)) {
    this->get_val = get_val;
}

void DTypeVar::setValue(void *v) {
    // empty
}

void DTypeVar::setValue(DType *v) {
    // empty
}

math_exp_type DTypeVar::resultType() {
    if (!this->get_val) return MATH_WILDCARD_VALUE;
    DType *t = this->get_val(this->name.c_str());
    if (!t) return MATH_WILDCARD_VALUE;
    return t->id;
}

DType *DTypeVar::eval() {
    if (!this->get_val) return nullptr;
    return this->get_val(this->name.c_str());
}

DType *DTypeVar::clone() {
    DTypeVar *c = new DTypeVar(this->name.c_str());
    *c = *this;
    c->left = nullptr;
    c->right = nullptr;
    c->parent = nullptr;
    return c;
}
...

For convenience, add a method in MathExprTree class to set get_val function. When the MathExprTree::setGetVal is called, instead of traversing every node in the tree, we will store variable nodes as a linked list in a tree for faster iteration.

// math_expr_tree.h
class MathExprTree {
private:
    ...
    std::list<DTypeVar *> vars;
public:
    ...
    MathExprTree(lex_data **postfix, int size, DType *(get_val)(const char *name)=nullptr); // add defult argument to the last parameter of constructor
    void setGetVal(DType *(*get_val)(const char *name));
    ...
};

// math_expr_tree.cpp
MathExprTree::MathExprTree(lex_data **postfix, int size, DType *(*get_val)(const char *name)) {
    lex_data *l;
    std::stack<MathExprNode *> s;

    for (int i = 0; i < size; i++) {
        l = postfix[i];
        if (l->token_code == MATH_SPACE) continue;
        assert(is_operator(l->token_code) || is_operand(l->token_code));
        if (is_operand(l->token_code)) {
            ...
            DTypeVar *var = dynamic_cast<DTypeVar *>(o);
            if (var) {
                this->vars.push_back(var);
            }
        } else if (is_unary_op(l->token_code)) {
            ...
}

void MathExprTree::setGetVal(DType *(*get_val)(const char *name)){
    for (std::list<DTypeVar *>::iterator it = this->vars.begin(); it != this->vars.end(); it++) {
        (*it)->set_get_val(get_val);
    }
}

Production rule for logical expression

Begin with the math production rule. To support unary (sqr, sqrt, sin, cos) and binary operators (max, min, pow), we need to modify our production rule to be like this.

E -> F + E | F - E | F
F -> T * F | T / F | T
T -> (E) | <var> | <int> | <double> | G(E) | P(E, E)
G -> sqr | sqrt | sin | cos
P -> min | max | pow

Then we can use the math production rule to construct the inequality production rule.

Q -> E INEQ E
INEQ -> == | != | < | <= | > | >=

After that, we can use the inequality production rule to construct the logical production rule

S -> S or J | J
J -> J and K | K 
K -> (S) | D | K LOP Q | Q LOP K
D -> Q LOP Q
LOP -> and | or

As you can see, our logical production rule suffers from left recursion. After removing left recursion, the production rule becomes.

S -> J S'
S' -> or J S' | $

J -> K J'
J' -> and K J' | $

K -> (S) K' | D K' | Q LOP K K'
K' -> LOP Q K' | $

D -> Q LOP Q
LOP -> and | or

Implement a calculator program

At this point, we can test our expression implementation by creating a calculator program as follows.

// calculator.cpp
extern parse_status E(); // math expression parser
extern parse_status Q(); // inequality expression parser
extern parse_status S(); // logical expression parser
extern lex_data **infix_to_postfix(lex_data *infix, int size_in, int *size_out);

// hard code the value of variable a, and b
DType *get_val(const char *name) {
    if (strcmp(name, "a") == 0) {
        return new DTypeInt(2);
    }
    if (strcmp(name, "b") == 0) {
        return new DTypeDouble(1.5);
    }
    return nullptr;
}

int main(void) {
    parse_status s;
    lex_data **postfix;
    int postfix_len;
    MathExprTree *tree;
    DType *res;
    lex_data d;

    while (1) {
        printf("input -> ");
        fgets(lex_buffer, sizeof(lex_buffer), stdin);
        stack_reset();
        s = S();
        if (s == PARSE_ERROR) {
            s = Q();
            if (s == PARSE_ERROR) {
                s = E();
            }
        }
        d = cyylex(); yyrewind(1);
        if (s == PARSE_ERROR || d.token_code != PARSER_EOL) {
            printf("invalid math expression\n");
            continue;
        }
        postfix = infix_to_postfix(lex_stack.data, lex_stack.top + 1, &postfix_len);
        tree = new MathExprTree(postfix, postfix_len, get_val);
        // tree = new MathExprTree(postfix, postfix_len);
        // tree->setGetVal(get_val);
        do {
            if (!tree->valid()) {
                printf("invalid math operation\n");
                break;
            }
            res = tree->eval();
            if (!res) {
                printf("cannot slove equation\n");
                break;
            }
            switch (res->id) {
            case MATH_INTEGER_VALUE: printf("%d", ((DTypeInt *) res)->val); break; 
            case MATH_DOUBLE_VALUE: printf("%f", ((DTypeDouble *) res)->val); break; 
            case MATH_BOOL: printf("%s", ((DTypeBool *) res)->val ? "True" : "False"); break;
            default: assert(0);
            }
            printf("\n");
        } while (0);
        delete tree;
        free(postfix);
        tree = nullptr;
        postfix = nullptr;
    }
    return 0;
}