Calculator for parentheses using recursion

#include 

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 real function 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.

Handling sub-expressions

The case where a `(' is found is handled by replacing this character, using ungetc, and then calling Expression. After all, the syntax says that the `(' is always followed by an expression and the function Expression reads the expression which follows and returns its value. It does not matter that we are inside the body of Expression; it can call itself, recursively.

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

Exercises on this section.


Next - Storage classes.

Back to Contents page.