#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