Given an expression E of n numbers with *, + operations and no precedence among the operators, find the max value of E

#include <stdio.h>


int nextNumber(char **s) {

int num = 0;

while(**s != '*' && **s != '+' && **s != '') {

num = num * 10 + (**s - '0');

(*s)++;
}


return num;

}

/*
    Algo:

    Let n0 n1 n2 n3 ... are the numbers in the expression E

    V(E) = max((n0 op V(E1)), ((n0 op n1) op V(E2))),

    Where E1 is the expression starting with n1 and E2 is the expression starting with n2
*/


//Assuming valid expression


int maxExpr(char *s) {

if(*s == '0')
return 0;

int num1 = nextNumber(&s);

char op = *s++;

if(op == '') {
return num1;
}

int val1 = maxExpr(s);

val1 = (op == '*') ? num1 * val1 : num1 + val1;

int num2 = nextNumber(&s);

int val2 = (op == '*') ? num1 * num2 : num1 + num2;

op = *s++;

if(op != '') {

num2 = maxExpr(s);
val2 = (op == '*')? val2 * num2 : val2 + num2;
}

return val2 > val1 ? val2 : val1;

}

/*
    Algo: This is a two pass algorithm
    
    In first pass evaluate all +
    Second pass evaluate all *
*/

int maxExpr(char *s) {

if(*s == '0')
return 0;

int n1, n2, n3 = 0;
char op;

char s2[strlen(s) + 1];
char *p = s2;

//First Pass
if(sscanf(s,"%d%c%d%n",&n1, &op, &n2, &n3) == 1) //only one number
return n1;


do{

if(op == '+') {
n1 += n2;
} else{
p += sprintf(p, "%d*", n1);
n1 = n2;
}

}while(sscanf(s += n3,"%c%d%n", &op, &n2, &n3) != EOF);

sprintf(p, "%d", op == '*' ? n2 : n1);

printf("%s\n", s2);
s = s2;
n3 = 0, n2 = 1;

//Second Pass

if(sscanf(s,"%d%c%d%n",&n1, &op, &n2, &n3) == 1) //reduced to one number
return n1;
do{

n1 *= n2;

}while(sscanf(s += n3,"%c%d%n", &op, &n2, &n3) != EOF);

return n1;

}

int main(){ char *s = "18+3*5+2*9"; printf("%d\n", maxExpr(s));}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s