Simple calculator

This program implements a simple calculator, which evaluates expressions such as:

• 1+2
• 3*4+1
• (4+5)*3
• 10 % 4 * 8

Programming Issues

Evaluating expressions such as these is a two part problem:

1. Parsing the input to determine the operators (such as +, -, * and /) and the operands (such as 1, 34, 112). Operators operate on operands.
2. Evaluating the expression according to the order of the operators and operands

Parsing the Input

In this program, parsing the input is relatively simple. Any sequence of digits is an operand, and anything else is an operator. We only allow single character binary operators in this program.

Note: a binary operator acts on two operands, such as 1 + 2, 3 / 5, or 3 * 6. A unary operator acts on only one operand, such as sqrt 5, or log 234.

In parsing our expressions, therefore, we will step through the input one character at a time, and:

• If we find a digit, we will consider the following sequence of digits to be one operand. We will continue parsing input from the next non-digit character.
• If we find a non-digit character, we will consider it to be an operator. We will continue parsing input from the next character, since all our operators are one character long.
• We will skip all whitespace.

With an expression such as 1 + 2 - 3 + 4, we could parse from left to right and evaluate as we go along, in the following manner:

However, this is not possible with an expression such as 1 + 2 * 4, as this should evaluate to 9 (as the multiplication should be carried out before the addition) and not 12 (as would happen in a simple left to right evaluation. In other words, some operators have a higher precedence than others. In addition, parentheses can be used to alter the "natural" precedence of operators, for example (1 + 2) * 3 which really would equal 12.

Evaluating complex expressions like this is not simple. However, the usual way of presenting expressions such as this, with its precedence rules and parentheses, is not the only way of representing expressions. We can make our life a lot easier by restating the expression in a more straightforward way before trying to evaluate it.

Postfix and Infix Expressions

An expression of the form (3 + 4) * 4 / 2 is known as a infix expression, and is the type used in everyday mathematics. It has a series of rules, such as multiply and divide operations are carried out before addition and subtraction operations, and subexpressions contained within parentheses are evaluated before any others.

A postfix expression is much simpler to evaluate. The postfix form of the above expression would be 3 4 + 4 * 2 /. While this may look strange, it's just another way of writing the same expression. In postfix, an operator appears after its operands (hence the word postfix), rather than in between them, as in an infix expression. There are no parentheses in a postfix expression, and no precedence rules (there is another form of expression called prefix, in which an operator comes before its operands).

The first thing we do in our calculator therefore, is to convert the input infix expression into a postfix expression. We do this in the following steps:

1. Create a stack data structure to temporarily store operators;
2. Read through the infix expression one token at a time from left to right;
3. Output an operand as soon as we come to one (operands always appear in the same order, whether we are using an infix, a postfix, or a prefix expression);
4. When we come to an operator, if it has a higher precedence than the operator currently on the top of the stack, then add it to the stack;
5. If the operator has a lower precedence than the operator on top of the stack, then remove operators from the stack one at a time until we run out, or until we come to an operator with a higher precedence.
6. When we run out of input, output any remaining operators still in the stack.

The one exception is that when we come to a closing parenthesis, we output all operators on the stack until we reach its opening parenthesis. In addition, even though we usually only place operators on the stack if the operator currently on the top has a lower precedence, we make a special case when an opening parenthesis is on the top of the stack. The opening parenthesis must have the highest precedence when parsing an expression, but the lowest precedence when at the top of the stack.

This will all be much easier to understand with a table. In the following example, we will assume '+' and '-' have a precedence of 1, '*' and '/' have a predecence of 2, ')' has a precedence of 3, and '(' has a precedence of 4, and we will convert our previous expression (3 + 4) * 4 / 2:

As you can see, our output is the postfix form of our original expression.

Evaluation

Once we have our postfix expression, evaluating it is fairly simple:

1. Create a stack, this time to hold the operands;
2. Read through the input from left to right;
3. If we find an operand, add it to the stack;
4. If we find an operator, remove the last two operands from the stack, perform the operation, and add the value back to the stack;
5. At the end of the input, the one remaining value on the stack is the result of our expression.

Again, in table format:

Summary

As you can see, evaluating a postfix expression is a lot simpler than evaluating an infix expression. Converting an infix expression to a postfix expression first makes the whole process much easier.

Usage

Execute as normal.

Source and Downloads

• View the C source in HTML format
• Download the tarred, gzipped source
• Download the zipped source

Home > Computer programming > C examples > Utilities > Simple calculator