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.

• CodeMaxx: Thanks for the pre-increment vs. post-increment thing. :) Some things though...The cast to int is not necessary, is it? We can have a switch statement for a character. Also the break; statement in default case can be removed.
• txtechhelp: @CodeMaxx strictly speaking, no, the explicit cast is not necessary, but I put it there to show that it's actually an implicit cast to an int (from char) .. as for the last break;, yes, strictly speaking it can be removed; but as a matter of habit, to avoid inadvertent switch fall-through's (and as a matter of explicit flow control), I always end every case/default statement with a break .. you can choose to leave it out if that's your personal preference though with the same effects
• CodeMaxx: But why is an implicit convert required when we are just comparing characters?
• Yuchen: I think static_cast<unsigned int>(..) is unnecessary too. What compiler are you using?
• txtechhelp: @CodeMaxx It's not "required", that's just what happens. The switch statement only works on integral types, thus the char type is implicitly casted in the switch statement to an int, and all case statements are also treated as such with each char type.