Programming Praxis

One of the most fundamental operations in computing is to evaluate an arithmetic expression, observing the precedences and associativities of the operators. For instance, given the expression 3+4*5, the multiplication is performed first, then the addition, giving a result of 23. Parentheses may change the order of evaluation, so that (3+4)*5 is 35. Today’s task is to write a program that takes as input a string containing an arithmetic expression and returns as output the result of evaluating that expression.

The usual approach to this task is to write a parser that identifies each element of the expression, evaluates them, and combines them into a solution. The parser is driven by a grammar that enumerates the various elements; the usual grammar for arithmetic expressions is:

expr -> term | expr + term | expr - term
term -> factor | term * factor | term / factor
factor -> number | ( expr )

Here -> and | are metasymbols of the grammar, +, -, *, /, ( and ) are operator literals, and expr, term, factor and number are operands; it’s not shown above, but a number is and integer consisting of either 0 or a sequence of digits not starting with 0, with an optional leading - sign. Blanks anywhere in the expression, even between the digits of a number, are ignored.

The evaluator consists of a set of mutually recursive functions that each recognize one metastatement of the grammar, plus a driver that accepts an input string and returns the result, all organized as dictated by the grammar.

As an example, consider the input string (3+4)*5. The driver passes the input to a function that recognizes expressions. Since the metastatement for expressions expects a term, that function immediately passes the input to a function that recognizes terms. Then, since the metastatement for terms expects a factor, that function immediately passes the input to a function that recognizes factors. That functions recognizes the opening parenthesis and calls the function that recognizes expressions to evaluate what is inside the parenthesis. Again, the expression metastatement looks for a term, and the term metastatement looks for a factor, and the factor metastatement looks for a number, which it finds, so it returns 3 to the term metatstatment, which returns 3 to the expression metastatement. Then the expression metastatement recognizes the + sign and goes next to the 4. The expression metastatement calls the term metastatement, which calls the factor metastatement, which identifies the 4 and passes it back to the term metastatement, which passes it back to the expressions metastatement, which adds it to 3 giving a result of 7. Now the expression metastatement is satisfied because the next input character is not a +, - or expression, so it returns the 7 to the expression that was called within the parentheses of the factor metastatement. The next character is a closing parenthesis, so the factor metastatement is complete, and passes back the 7 to the term metastatement. Now the next character is *, which is recognized by the term metastatement, which passes the remainder of the input string, the 5 character, to the factor metastatement. Now the factor metastatement recognizes the number 5 and returns it to the term metastatement, which multiplies it by 7 producing a result of 35. The result is passed back to the expression metastatement, which recognizes that the expression is complete, so it passes the result 35 back to the driver function, which outputs the result. Whew! Aren’t you glad you have a computer to do all of that work for you?

Your task is to write a function that evaluates an infix arithmetic expression. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2