6. Writing a Program

Working on a problem, we typically repeatedly go through these stages:

• Analysis: What does a solution to our problem look like? What features must it include? What features would be nice to include?
• Design: How do we break the system into comprehensible parts to achieve the goals analysis has revealed to us?
• Development: Write the code that implements our design, and debug and test it.

Some suggestions:

• Take the user's point of view and ask what the program is for. If you were using it, how would you like it to work?
  • Is the problem clear? Are we asking for too much? (Best to build an MVP, and then improve it based on user feedback.)
  • Can we really tackle this project, given our time, resources, knowledge, etc.? No point in taking on something you can't possibly complete!
• Break the program down into manageable parts.
  • Can we use existing tools, libraries, etc. that might help? If so, always use them! How do we know if they are worth adopting? Ask friends, ask Google, look on StackOverflow.
  • Look for parts of the solution that can be separately described and potentially re-used. Correctly identifying such parts requires experience: that is why we present you with many examples.
• Build a small, limited version of the program that solves a key part of the problem.
  Why?
  • This will force to the surface misapprehensions in our understanding of the problem we wish to solve. Ultimately, the computer itself is the measure of our design!
  • We also may need to change some aspects of the design to make our problem manageable: perhaps the "ideal" spec involves using an exponential algorithm, but in fact we can come "close enough" with a polynomial one.
• Build a full-scale version, using parts of the initial version. Our ideal: Grow a program from working parts.

Well, we are anxious to start writing code, so let us try:

#include "std_lib_facilities.h"

int main()
{
    cout <<"Please enter an expression (we can handle + and -):\n";
    int lval = 0;
    int rval;
    char op;
    int res;
    cin >> lval >> op >> rval; // read e.g. 1 + 3

    if(op=='+')
        res = lval + rval;
    else if(op=='-')
        res = lval - rval;

    cout << "Result: " << res << '\n';
    keep_window_open();  // if necessary on your system!
    return 0;
}
                            

lval is our variable for the left-hand value, and rval for the right-hand value.
Well, we have something (kind of) working!
Let's improve our program by:

1. Clean up our code
2. Add multiplication and division
3. Add the ability to handle more than one operand (e.g., 1+2+3)

So let's try this:

#include "std_lib_facilities.h"

int main()
{
    cout << "Please enter an expression (we can handle +, -, *, and /):\n";
    cout << "Add an x to end expression (e.g., 1+2*3x): ";
    int lval = 0;
    int rval;
    int res;
    cin >> lval;
    if(!cin) error("No first operand!");
    for(char op; cin >> op;) {   // repeatedly read ops
        if(op!='x') cin >> rval;
        if(!cin) error("No second operand!");
        switch(op) {
        case '+':
            lval += rval;
            break;
        case '-':
            lval -= rval;
            break;
        case '*':
            lval *= rval;
            break;
        case '/':
            lval /= rval;
            break;
        default:
            cout << "Result: " << lval << '\n';
            keep_window_open();  // if necessary on your system!
            return 0;
        }
    }
    error("Bad expression");
}
                            

Problems:

1. We accept multi-line expressions.
2. Our operator precedence is wrong! But how do we find the "correct" operator amongst all input?
3. How do we remember the place of each op?
4. How do we avoid proceeding strictly left-to-right?

We are going to tokenize our input to get this right! Token will be our first user-defined type. We will initially define:

• Floating point numbers: 1.23, 0.274e2, 42
• Operators: +, -, *, /, %
• Parentheses: (, )

Tokens will hold a kind and a value (for floats).

Our initial definition of Token:

class Token {
public:
    char kind;
    double value;
};
                            

We can initialize (construct) Token objects like this:

Token t1 {'+'};
Token t2 {'8', 11.5};
                            

We will read a stream of tokens into a vector, so we need:

Token get_token();  // read token from cin

vector<Token> tok;

int main()
{
    Token t = get_token();
    tok.push_back(t);
}
                            

OK, we have tokens: now what? This helps us sorting out the text into pieces, but how do we get the order of evaluations correct? And can we support variables? We'd better back up and think some more.

To wrap our heads around this, let's make a simplistic grammar for English:

Sentence:
    Noun Verb
    Sentence Conjunction Sentence
Conjunction:
    "and"
    "but"
    "or"
Noun:
    "birds"
    "fish"
    "C++"
Verb:
    "rules"
    "fly"
    "swim"
                            

We can now make sentences like "C++ rules but fish swim."

A grammar for lists:

List:
    "{" Sequence "}"
Sequence:
    Element
    Element "," Sequence
Element:
    "A"
    "B"
                            

According to that grammar, which of the following are valid lists, and which not?

{ A }
{ }
A, B, A, B
{ A, B, B, B }
{ A, B, B, B, }
{ A B B B }
                            

We are going to try to turn our grammar rules into working C++ code. I will offer you pseudo-code for each of the elements of the grammar in what follows. What we will need to implement this grammar is:

1. A way to get the next token of input.
2. A function to implement the expression rule: expression().
3. A function to implement the term rule: term().
4. A function to implement the primary rule: primary().

So let's look at pseudo-code version of 2-4: we will create a new class to handle 1.

Expression pseudo-code:

double expression()
{
    left = term();
    Token t = get_the_next_token(); // we will see how to do this later!
    while(true) {
        switch(t.kind) {
            // here we need cases to handle + and -
            // the default case will return left
        }
    }
}
                            

Term pseudo-code:

double term()
{
    double left = primary();
    Token t = get_the_next_token(); // we will see how to do this later!
    while(true) {
        switch(t.kind) {
            // here we need cases to handle * and /
            // the default case will return left
        }
    }
}
                            

Primary pseudo-code:

double primary()
{
    Token t = get_next_token; // we will see how to do this later!
    switch (t.kind) {
    case '(':    // handle '(' expression ')'
        {    
// here we will expect an expression, and then a ')':
// you must write this switch so as to handle that
            return d;
        }
    case '8':            // we use '8' to represent a number
        return t.value;  // return the number's value
    default:
        error("primary expected");
}

                            

Here is an implementation of Token_stream:

class Token_stream {
    public:
        Token get();
        void putback(Token t);
    private:
        bool full{false};
        Token buffer;
};

void Token_stream::putback(Token t)
{
    buffer =t;
    full = true;
}

Token Token_stream::get() {
    if(full) {
        full = false;
        return buffer;
    }
    char ch;
    cin >>: ch;
    switch(ch) {
        case ';':
        case 'q':
        case '(': case ')': case '+': case '-': case '/': case '*': case '%':
            return Token{ch};
        case '.':
        case '0': case '1': case '2': case '3': case '4':
        case '5': case '6': case '7': case '8': case '9':
        {
            cin.putback(ch);
            double val;
            cin >>: val;
            return Token{'8', val};
        }
        default:
            return Token{'i', double(ch)};
    }
    return Token{'q'};
}
                            

Most tokens we recognize by simply seeing the character that represents that token.

However, when we see a digit, we want to take advantage of the C++ facility to read a double for us: thus, we push the digit we read back onto cin, and then try to read a double from cin.

1. a; 2. a; 3. c; 4. c; 5. b; 6. b; 7. c; 8. c; 9. b; 10. b; 11. d;