C language expressions

Although expressions can be made up of data of any type, only numerical expressions are considered in this chapter. For our purposes, we will agree that numeric expressions will consist of the following elements:

• Numbers
• Operators (operations signs) + , - , / , * , ^ , % , =
• Parentheses
• Variables

The ^ operator means exponentiation, as in the BASIC language, and the symbol = denotes an assignment operator. These elements can be combined into expressions according to the rules of algebra, for example:

  10 - 8
 (100-5) * 14/6
 a + b - c
 10 ^ 5
 a = 10 - b

Let operators have the following priority:

  higher unary + and -
            ^
            * /%
            + -
 lower =

If the expression contains operators that have the same priority, then the calculations are performed from left to right ^[1] .

In the examples in this chapter, all variables have names of the same letter (in other words, 26 variables are allowed, from A to Z ). Variable names are not case sensitive (uppercase or lowercase). For example, a and A denote the same variable. Each numeric value is of type double , although it is not difficult to write procedures for processing values ​​of other types. Finally, to keep the program logic simple and straightforward, only minimal error control will be performed.

If you have not thought about the process of parsing expressions, try to evaluate the following expression:

  10 - 2 * 3 

You know that it is equal to 4. Despite the fact that you can easily create a program that will calculate this particular expression, the question is how to write a program that gives the correct result for an arbitrary expression. In the beginning, the following algorithm may occur to you:

  a = get first operand
 while (there is an operand) {
   op = get opretor
   b = get second operand
   a = a op b
 }

This procedure takes the first operand, the operator and the second operand, performs the first operation on them, then reads the next operator and operand (if any) and performs the next operation indicated by the received operator, etc.

However, with this approach, when calculating the expression 10 - 2 * 3, the result is 24 (that is, 8 * 3) instead of 4, because the procedure described does not take into account the priority of the operators. One cannot simply choose operands and operators from left to right, since the rules of algebra say that multiplication is done before subtraction. Some novice programmers think that this problem is easy to overcome. In very rare cases, they succeed. But the problem becomes more complicated when brackets are added, exponentiation, variables appear, functions are called, etc.

Despite the fact that there are several ways to write an expression evaluation program, the method we are describing is the simplest for human coding. It is also the most common. (In some other methods of creating parsers, they use complex tables generated by another computer program. Such analyzers are sometimes called table-driven.) The method described here is called the recursive descent method, and by reading the chapter, you will undoubtedly guess why it is so called.

^[1] However, there is one frequently occurring exception - the exponentiation operator. X ** Y ** Z means, as a rule, not (X ** Y) ** Z, but X ** (Y ** Z). (Operator ** is the usual notation for the exponentiation operation in many programming languages, the most common of which is Fortran.) Exactly the same thing happens in algebra: the expression a ^{b c} means a ^{(b c )} but not (a ^b ) ^c = a ^{b c} .