Parsing a string containing arithmetic operations in prefix notation

Question

This is a piece from the complete program. What it does is parses mathematical expressions of the form (+(*3,x),5) to 3*x + 5 and store it in an object of class Formula. Add,Mul, Div, Exp, X, Integer and Symbols are derived from Formula class. Recursive strategy has been used to parse formulae with greater complexity.

Please request for any other piece of code if required.

Does this code have redundancy? How can it be improved?

void parse(Formula*& f, string s, int &k)
{
    if(s[k] == '(')
    {
        k++;
        if(s[k] == '+')
        {
            f = new Add();
        }
        else if(s[k] == '/')
        {
            f = new Div();
        }
        else if(s[k] == '-')
        {
            f = new Sub();
        }
        else if(s[k] == '*')
        {
            f = new Mul();
        }
        else
        {
            f = new Exp();
        }

        k++;
        parse(f->left, s, k);
        k = k + 2;
        parse(f->right, s, k);
        k++;
    }
    else
    {
        if(s[k] == 'x')
        {
            X* a = new X();
            f = a;
        }
        else if(48 <= s[k] <= 57)
        {
            Integer* a = new Integer();
            a->i = s[k] - 48;
            f = a;
        }
    }
}

Answer 1

First, since you're parsing strings at the character level, you could cast the character to an int and utilize a switch statement to check the values (vs. an else if which checks each branch), e.g. switch (static_cast<unsigned int>(s[k])). Also, unless there's a specific need, it's advisable to prefer the pre-increment vs. post-increment operators, e.g. ++k vs. k++. These 2 changes are for speed optimizations (since you are doing parsing). For the static_cast of the char type, strictly speaking, you do not need the explicit cast to an int type, that's there for explicitness (pedant/completeness/explanation) since switch statements only work on integral types, thus any type that can be converted is (either implicitly by the compiler, or explicitly by the user).

Also, there's a logic bug in your code, the line that reads else if(48 <= s[k] <= 57) will always be true. This line evaluates to the following: else if ((48 <= s[k]) <= 57) .. take note of the added parenthesis. Essentially you're asking if a boolean value is <= 57 which is always true. This line should read as such: else if ((48 <= s[k]) && (s[k] <= 57)).

The following is the updated code:

void parse(Formula*& f, std::string s, int &k)
{
    switch (static_cast<unsigned int>(s[k])) // explicit cast
    {
        case '(':
        {
            switch (s[++k]) // implicit cast
            {
                case '+': f = new Add(); break;
                case '/': f = new Div(); break;
                case '-': f = new Sub(); break;
                case '*': f = new Mul(); break;
                default:  f = new Exp(); break;
            }
            parse(f->left, s, ++k);
            k = k + 2;
            parse(f->right, s, k);
            ++k;
        } break;
        case 'x':
            f = new X();
            break;
        default:
            if ((48 <= s[k]) && (s[k] <= 57)) {
                f = new Integer();
                (static_cast<Integer*>(f))->i = s[k] - 48;
            }
            break;
    }
}

Again, I don't have your complete code so these semantics might need to be adjusted for your specific case, but in general this cuts down branch prediction and temporary usage (which the compiler can then optimize further).

Hope that can help.