Chapter 9. Formula Interpretation

The spreadsheet program is capable of handling text, numerical values, and formulas composed by the four arithmetic operators. In order to do so, we need to interpret the formulas. We also need to find the sources of a formula (the cells referred to in the formula) and the targets of a cell (the cells affected by a change).

In this chapter, we will take a look at the following topics:

• Interpretation (scanning and parsing) of numerical expressions

• Parse and syntax trees

• Evaluation of formulas

• References and matrices

• Drawing of cells

• Loading and saving of cells

In the following spreadsheet, the C3 cell is being edited:

Formula interpretation

The core of a spreadsheet program is its ability to interpret formulas. When the user inputs a formula in a cell, it is interpreted and its value is evaluated. The process of formula interpretation is divided into three separate steps. First, given the input string, the Scanner generates a Token List, then the Parser generates a Syntax Tree, and the Evaluator determines the value.

A token is the least significant part of the formula. For instance, a1 is interpreted as a reference and 1.2 is interpreted as a value. Assuming that the cells have values according to the following sheet, the formula interpretation process will be as follows. Remember that a formula is text beginning with an equal sign (=).

The tokens

The scanner takes a string as input and finds its least significant parts-its tokens. Spaces between the tokens are ignored, and the scanner makes out no difference between capital and small letters. The Value token needs an extra piece of information...

Matrix and reference

The Matrix class is used when storing the cells of spreadsheet, and the Reference class is used when accessing cells in the spreadsheet.

The reference class

The Reference class holds the row and column of a cell in the Matrix class, as shown in the next section:

Reference.h

namespace SmallWindows { 
  class Reference; 
  extern const Reference ZeroReference;  

  class Reference { 
    public: 

The default constructor initializes the row and column to zero. A reference can be initialized by and assigned to another reference:

      Reference(); 
      Reference(int row, int col); 
      Reference(const Reference& ref); 
      Reference& operator=(const Reference& ref); 

The compare operators first compare the rows. If they are equal, the columns are then compared:

      friend bool operator==(const Reference& ref1, 
                             const Reference& ref2); 
      friend bool operator...

The cell

The cell can hold three modes: (possible empty) text, a numerical value, or a formula. Its mode is stored in the cellMode field. It can hold the value TextMode, ValueMode, or FormulaMode. Similar to CalcDocument in this chapter and WordDocument in the previous chapters, we refer to the current value of cellMode in expressions such as in text mode, in value mode, and in formula mode.

HeaderWidth, HeaderHeight, ColWidth, and RowHeight are the size of the headers and cells of the spreadsheet. In order for the cell text to not overwrite the cell's borders, CellMargin is used. The spreadsheet is made up of ten rows and four columns.

Cell.h

extern const int HeaderWidth, HeaderHeight, 
                 ColWidth, RowHeight, CellMargin; 
 
#define Rows 10 
#define Cols 4 

A cell can be aligned at the left, center, right or justified in the horizontal direction, and it can be aligned at the top, center, or bottom in the vertical direction:

enum Alignment {Left, Center...

Further reading

If the scanner and parser of this chapter have got you interested in compilers, I recommend that you refer to Compilers: Principles, Techniques, and Tools by A. V. Aho et al. (second edition. Addison Wesley, 2007). It is the second edition of the classic Dragon Book. The authors explain the theory and practice of compilers from scanning and parsing to advanced optimization.

If the concept of graphs has caught your interest, I recommend Introduction to Graph Theory by D. B. West (Prentice Hall, 2000), which reasons about graphs from a mathematical point of view.

Summary

In this chapter, we covered the spreadsheet program implementation. This chapter concludes the first part of this book: how to develop an application with Small Windows. Chapter 10, The Framework, introduces the second part: the implementation of Small Windows.