First here is a full syntax for arithmetic expressions.
expression term expression + term expression - term term factor term * factor term / factor factor identifier constant ( expression )These definitions contain the recursive use of expression within parentheses and we wish to isolate this from the problem of operator precedence, which is implied by the separation into factors and terms each with their own set of operators. Thus below is a simplified syntax for our purposes. This also removes the non-constant definitions of factor.
expression factor factor + expression factor - expression factor * expression factor / expression factor constant ( expression )We are left with a problem which is solved by the following program.
#includePlain text to compile and run.float Expression() { char Operator, nextc; float Answer, NewNumber; Answer =0; Operator ='+'; while ((Operator!='=') && (Operator!=')')) { nextc = getchar(); if (nextc=='(') NewNumber =Expression(); else { ungetc(nextc,stdin); scanf("%f",&NewNumber); } switch (Operator) { case '+': Answer += NewNumber; break; case '-': Answer -= NewNumber; break; case '*': Answer *= NewNumber; break; case '/': Answer /= NewNumber; break; } /* switch */ Operator = getchar(); } /* end while loop */ return Answer; } /* end Expression */ void main() { printf("Final answer is %f\n",Expression()); }
The main program consists of a single statement, which is a call on printf. This has two parameters, the first simply a string constant, the second a call on the function float Expression.
Expression reads in and evaluates an expression. It allows any of the operators in our syntax. It terminates when it finds either a closing parenthesis, ')', or an equals sign, '='.
So long as the expression contains no parentheses, this program operates in the same way as our earlier calculator example. The difference is what it does with such sub-expressions. Note that the syntax only allows a left parenthesis, '(', at the start or after an operator, i.e. in the same place as a constant value. This means that we need to be able to look at the next character, to see if it is a left parenthesis, without necessarily keeping it.
The ungetch() puts back the last character read in. Thus, we can check if it is a '(' and still read it as the first character of a number if it is not. This is very useful, even if the idea used seems rather odd.
The second call of Expression is started by a '(' and ended by a ')'. It can never find a legal '='; only the first call of Expression can end with that. In fact it will end with the matching ')', even if there is another nested sub-expression inside this one.
To see this, let us examine an example. The expression (2+3*(3-(2-1))) would result in the following sequence:
"2+3*(3-(2-1))=" Call Expression #1 from scanf in main 0+2=2; 2+3=5; Find ( with Operator='*' and Answer=5 "3-(2-1))=" Call Expression #2 0+3=3; Find ( with Operator='-' and Answer=3; "2-1))=" Call Expression #3 from Expression #2 0+2=2; 2-1=1; Find ) ")=" End Expression #3 Return 1 to Expression #2 3-1=2; Find ) "=" End Expression #2; Return 2 to Expression #1 5*2=10; Find = "" End Expression #1 Return 10 to printf in main