Decisions, Structures, Logic

See also

Text: Chapter 4

Back in Input - Process - Output we saw three basic programming tools that all programmers use. These are called the “structures” of programming. Only three are needed, but we use variations of some of them for convenience!

Since we are not writing real programs yet, we will explore these structures using the idea of “pseudo-code” as a way for you to write down your ideas on how to solve a problem.

Note

Your text shows diagrams (flow charts) for all of these structures. Since we do not have a tool that will help you build these charts, I am not going to ask you to draw them for this class. (You would have to scan them, or take pictures of them to send to me. Not fun!) Use them if it helps your thinking. I find pseudo-code easier to write down. YMMV!

Pseudo-Code

Pseudo-code has no formal rules on how you write it. Your goal is to write as clearly as you can, eliminating anything that might cause confusion in the mind of the reader. In fact, that is a good way to test your pseudo-code. Get someone else to read it and see if they think they could follow your instructions and get the job done. They have to understand your instructions, and you have to believe that your process will do exactly what is needed to get the solution you are after.

Real programmers probably do not really write a lot of pseudo-code in their work. Instead, they use something closer to programming notation to write down their thoughts. In fact, I tend to use Python to do just that, even if I am going to eventually write my program in another programming language like C++.

Pseudo-code is an attempt to reduce the baggage of human speech into short, crisp phrases clearly stating what to do. We do not want any fluff in what we write down. So, instead of this:

Have the user enter a number representing the number of bedrooms they want
in their new house.

We do this:

Enter NumberOfBedrooms

And, instead of this:

Add up all the checks and deposits in the pile on your desk to get the
final balance you should see in your checkbook.

We might write… What?

Enter basic structures

This last sentence is hard to simplify, because it has several parts buried inside a simple sentence. Humans might be able to charge off do the job, but the end result might not be what you have in mind. For one thing, you might really want to see the total of all checks written, and the total of all deposits made, even though the sentence above does not mention that. It could be that these two numbers are on your bank statement, and it would be nice to check your work more closely than just figuring out the final balance you should see in your checkbook!

So, how do we take this sentence apart and simplify it?

We will do so with just our basic three structures:

  • Sequence of statements
  • Decision (if-then-else)
  • Loop (repeat some operation until we say to stop)

Our job is to find a way to write down a small set of crisp instructions that will do the job we really want done.

Characteristics of Structure

There is one very important characteristic of each of the structures. It might be easier to spot if we look at diagrams for all three:

Sequence:
../_images/Sequence.png
Decision:
../_images/Decision.png
Loop:
../_images/Loop.png

Look at each of these and see if you can spot the common characteristic. As simple as it might seem, the key thing about these is that each one has:

  • A single point of entry
  • A single point of exit

Before these structures were introduced, programmers used a form of statement called a “GOTO” which had a line number after it. Each line of code was numbered and you could just leap from anywhere in your program to anywhere else! The effect of this was that you could put your finger on a line of code and have no idea how you might get there in your program. Believe me, we used flow-charts a lot back then to figure out where our code was going. (I remember taping pages all over the wall of a study room in college trying to figure out how a big program I got from NASA worked. It was a mess to figure out! We even called this mess “Spaghetti Code”!

Programmers practically went nuts when they were told those days were over. All programming was to be done with just the basic three structures (with a few convenience additions that were not really necessary, just handy). It was finally proven that they could still get the job done, they just had to learn to think differently.

They did learn, and hardly anyone wants to go back to the old ways!

You can learn this, today!

Designing a Solution

We will use that weird sentence shown above, and tear it apart using the three basic structures. The idea is to learn how to spot something in the problem that leads you to pick one of these structures and apply it to the solution.

Here it is again:

Add up all the checks and deposits in the pile on your desk to get the
final balance you should see in your checkbook.

Picking a Structure

Faced with a problem, even a simple one like the sentence above, we start off by looking closely at the sentence. We are looking for a piece to carve off.

Which structure should we use?

Well, the first three words of our sentence give us a big clue: “Add up all”

Those words tell us that we have a number of items to process, and that calls for a loop!

In the example I am going to show here, I am going to use a few simple terms to set up my pseudo-code. Here they are:

1. Sequence: Nothing needed here, just a short phrase followed by another short phrase. We could number each step, so we can see the order we are to do them in! Actually, I seldom do this, the order is implied in the list of steps.

  1. Decision: We call this an IF_THEN_ELSE Structure:

    IF (something is true) THEN
        do something
    ELSE (that something is not true)
        do something else
    ENDIF
    
  2. Loop: The most common one is the WHILE Loop:

    WHILE (something is true) DO
        The work to do each time through the loop
    ENDWHILE
    

Those capitalized words are not actually required by pseudo-code, you are free to use any notation you like. I use these names because they are common in real programming languages. Anything else I put in my pseudo code can be short, English-like phrases. (I am not going to say sentences, since those things have too many unneeded words!)

Let’s take our three words and try to set up part of our pseudo-code:

WHILE (there is an item to process) DO
    process item
ENDWHILE

Hmmm, what is an item? In my thinking, it is a check or a deposit.

Now, I have started writing down my pseudo-code with a loop. But, is this actually where I will start?. Actually, no! I am supposed to come up with a final balance. That implies I need to get an initial balance and use that to calculate the final balance. So, what I really need is a sequence that looks like this:

Enter InitialBalance
While (there is an item to process) DO
    process item
ENDWHILE
display FinalBalance

Here, I am coming up with simple names for data containers I will use in my code. The names are supposed to be readable, and they are, since I am using words that make sense in the context of the problem I am solving. I just mash those words together and capitalize the first letter of each word. Notice that I am not worrying about the “type” of the data I am working on here, that will come later.

Finding Totals

Let’s assume we do want to add up all the checks and deposits to see the total of each we had this month. What do we do to add this feature. For now, just this:

Enter InitialBalance
Set TotalChecks to 0
set TotalDeposits to 0
WHILE (there is an item to process) DO
    process item
ENDWHILE
display FinalBalance
display TotalChecks
display TotalDeposits

See those new variable names? In order to come up with a total, we have to start off by setting a named data item to zero, then add each data item needed to that value. This is exactly what you would do with a calculator. You would initially “clear” the calculator, then add in the new items , one at a time, until you are done. The final number in the calculator is your total. The name we have chosen for our total is where the numbers from the calculator will be saved. Actually, we say we “accumulate” the final total, since it builds up in our loop.

Hmmm, so far things look fairly good. However we need to do some work inside that loop.

Controlling the loop

We have a phrase inside the parentheses on the line where we start our loop. The loop works by evaluating that phrase to see if it is true or false. How do we know if there is an item to process?

The common way, which we have discussed before, is to ask the user of our code to enter an amount. As before, we will use a positive number to indicate a deposit, a negative number to indicate a check, and zero to indicate there are no more items to process. Hey, I just answered my own question. I will ask the user to enter an amount from the item according to our rules, and see if it is zero or not!

Here is my revised code:

Enter InitialBalance
Set TotalChecks to 0
set TotalDeposits to 0

Display instructions to the user

Enter ItemAmount
WHILE (ItemAmount is not zero) DO
    process item
    Enter ItemAMount
ENDWHILE

display FinalBalance
display TotalChecks
display TotalDeposits

Notice that I have added blank lines to separate the major sections of my code. The top block is getting set up to work. This helps tell the reader that a new activity is being processed. Next, we prompt the user, telling them what to do. Then we process all the data. Finally, we generate out final output. Arranging our code this way helps readers understand the code, as does picking good variable names!

Notice that I added a line to remind me to generate a “prompt” telling the user what to do when this program runs. Users do not like staring at a screen with no idea what to do!

Warning

In real programs, never, NEVER, trust the user to do what you tell them to do. There are users (who might actually be trolls) who will try to break your program, just for fun! Be smarter than them! Use something called “input validation” to verify that what they typed in matches what you need! This is important. We will explore more on this later.

Pre-seeded Loops

The pattern we are using to control the loop is very common. It is the pre-seeded loop.

Let’s assume the user is not a troll, and will enter a good number when asked. We start off by reading an initial item value. We call this first value the “seed” value. It might be positive, meaning a deposit; negative, meaning a check; or zero, meaning we are done!

If we had no activity this month, the loop logic will work fine. The final balance will equal the initial balance.

If we have an item to process, the entered amount stored in ItemAmount will not be zero, and we will enter the loop. The first thing we do is process the current item (the one whose value we just read). Once we are done processing the item, we ask the user to enter the next ItemAmount. If there are no more, the user will enter zero.

If there are more items, the next amount will be entered and stored in ItemAmount. The loop spins back up to the question and we see if we are to process again. This repeats until we run out of items.

Just what we want.

Looks like this is going to work.

Time Out

We need to stop a moment and consider what we have been doing. On each step, I added something to the pseudo-code, usually a single new phrase, or at most a few phrases in a simple pattern. I am clarifying my thinking by making things more precise. I am replacing English with simpler English. Hopefully, there is less room for making a mistake in understanding what we want to do!

If we were doing all this using flow charts or a real programming language, we would have been even more precise. Our questions would have been posed in something more nearly code, since that is what is required there. However, in pseudo-code, we can stay with simple English phrases that we understand will evaluate to true or false.

Drawing boxes

One thing we can do with a properly structured pseudo-code program that will highlight the structure is to draw boxes around each structure. These boxes will nest nicely, there will not be any boxes crossing over other boxes. You will see that we have structures inside of other structures. That is how we refine our thinking.

Structures in Flow Charts

We can even do this when using “flow charts”.

In those structure diagrams above, you see only two basic shapes connected by flow lines. The diamond is where we ask a question. There will be one entry point into the diamond, and two outputs, one for a true answer, and one for a false answer. To make this a structure, we have each of these lines go to a separate box, and then we require that the flow out of these two boxes join together to form a single exit flow out of this structure.

A sequence is just one or more boxes in a line. And the loop starts off by asking a question in a diamond, then flowing to a box only if the question evaluates to true. After we leave the box, we go back and ask the question again. Only when the answer is false do we “fall out” of the loop. Once more, we have a single entry and a single exit.

Here is the key concept. Inside any box you see in your diagram, you can put another structure in that box. I replace a one statement sequence with three statements, and will replace logic inside the loop with another sequence as we figure that part out.

A box has a single point of entry and a single point of exit. So does each of our structured forms, which is why we can put any structures into these boxes. There are tools to hep you build flow charts, but they are far too complex for a beginner’s course. They rearrange things so you can see the result of this refinement process. In the old days, we wadded up paper drawings, threw them away, and drew them over. We wasted a lot of paper doing all of that!

OK, Back To Work

We are close to finishing our pseudo-code. We have everything set up to do the last small bit of work. Once we have an item in hand, and we are in the loop body where we are to process the work, we have a question to ask. Is this a check, or a deposit?. Here is how we deal with that:

Enter InitialBalance
Set TotalChecks to 0
set TotalDeposits to 0

Display instructions to the user

Enter ItemAmount
WHILE (ItemAmount is not zero) DO
    IF (ItemAMount is greater than zero) THEN
        process deposit
    ELSE
        process check
    ENDIF
    Enter ItemAMount
ENDWHILE

display FinaBalance
display TotalChecks
display TotalDeposits

Notice that we do not worry about the ItemAmount being zero, we eliminated that possibility in our initial loop question. So, our IF-THEN-ELSE has only to deal with positive or negative amounts. If it is not one, it must be the other!

Do you think you can see how to complete this logic? We still need to add up things, then calculate the final balance. The totals can be worked up inside the decision block, and the final balance can be calculated when we leave the loop, just before we display the final answer!

Starting and Stopping

One last point. Your pseudo code starts at the top, on that first line. In some notations, we would put the word START there to show where we start. Where do you stop?

The right answer is at the end of the code. A properly structured program always ends at the bottom, not in the middle somewhere. It would be easy to see a way to generate the output we need inside the loop. We would update the final balance with each item we process and print that out. When we finally saw that last ItemAMount of zero, we would just stop. However that would have us writing the word “STOP” in the middle of our code, giving us a kind of “jump” to some exit point. This is not allowed in structured programming.

Approaches to Design

How you think through the solution to a problem is something you have to decide. There are two basic approaches:

Top Down

We should work on our logic to make sure we have a proper way to start work, and a proper way to stop work. You can use this “top-down” approach to building nay program. You start off by looking at the big picture and work your way down to the details. That is essentially how I did things here.

Bottom Up

Another approach is to work “bottom-up” where you start with details and build up to a complete program. For beginners, it makes more sense to work top-down as we did in this example.

Structures seem to impose rules on you, and some folks balk at that. “We don’t need no stinking rules!” Well, in some circles that may be true, but in programming, it has been shown over and over, that humans build better programs, and get more accurate results if they follow the simple rules of structured programming. As you do more of this, I believe you will see that!

Indenting

Along with structures, programmers started doing something else when they converted their diagrams to real code. They started “indenting” things. Do you see how indenting makes it more obvious what part of the pseudo-code is happening during the true part or an IF-THEN-ELSE structure, and what part is happening during the false part? Indenting is an important part of programming, even when using languages that do not really care about things like that.

A simple fact of life in programming is that humans read programs far more than computers do. It is important to make your code “readable”, and each language has a preferred style for how things should be presented. In today’s world of programming, indenting is done with exactly four spaces (not tabs) and folks will look at you funny if you do otherwise. You are not really writing a program for yourself, most of the time. It is for the poor soul who will have to maintain that program long after you have moved on. Surprisingly, that may be you in a few months, when you have forgotten that you even wrote this thing!

I am Sick of Checkbooks!

Me too!. Let’s try something else. Before we leave this lecture, let’s solve another problem using some real code!

How about a programmable thermostat. (I am sitting in my living room looking around for a problem to try out! It was there, on the wall, just staring at me!)

Here is a problem statement:

Write a program for a thermostat with two buttons: one to increase the temperature, and one to decrease the temperature. The thermostat has a temperature sensor that can report the current temperature, and a display showing the temperature we want the house to have. The thermostat can turn on the heat, or the air conditioner.

Sounds simple enough. What structures do you see here. Is there a loop, is there a decision to make, is there input? Is there output? Phew, that is a lot to consider.

Once again, use your own sense of what has to happen to see what needs to be done by our program.

Just for fun, rather than use our pseudo-code again, I will show you a Python program that might do this job:

# Thermostat program

# This program assumes that several modules are available to deal with
#   human interactions:
#
#   currentTemperature()     - reads the current temperature sensor
#   ActivateHeat()           - turns on the heat
#   ActivateAirConditioner() - turns on the air conditioner
#   ButtonUpPressed()        - is the user holding down the up button?
#   ButtonDownPressed()      - is the user holding down the down button?

currentSetting = currentTemperature()
while True:
    if Temperature() > currentSetting:
        ActivateAirConditioner()
    elif Temperature() < currentSetting:
        ActivateHeat()
    If buttonUpPressed():
        currentSetting = currentSetting + 1
    if buttonDownPressed():
        currentSetting = currentSetting - 1

Those lines beginning with a sharp character are comments, ignored by the language. Everything else is code.

Note

Python is a language that requires the use of indenting to show the structure of the program. That “while True:” line is a while loop and everything below that line is indented. That means that all code indented below that point is inside the loop. There are structures inside other structures here, and the code for those inner structures is indented more.

When will this loop end? Never! I do not want my thermostat to take a vacation!

Asking Questions (Decisions)

We always need to ask questions in our programs. We need to know what is going on, so we examine the data to find out.

All questions in programs have answers that are either “true” or “false”. No “maybe” allowed.

We call these questions “boolean”, and we can ask complex questions as long as they end up producing “true” or “false” only.

Boolean Expressions

Expressions are those constructs that have to be “evaluated” to produce a final value. Math expressions are the most common:

  • 4 * a + b

In this expression, we are supposed to look up the value stored in the containers “a” and “b”, and evaluate the result of doing this math! The expression will generate a final value that is a number (integer). (See chapter 2 for details about how this works. We will explore math in a later lecture.)

When we ask questions in our programs, we will set up similar expressions, but the evaluation will not result in a number, it will result in a value of “true” or “false”. Those are “boolean expressions”

Relational Operators

We have several questions in our example code, and we are using notation called “relational operators”:

  • “>” means “is greater than”
  • “<” means is less than”

These are used to form statements that are either true or false.

There are other “relational operators” available:

  • “>=” means “is greater than, or equal”
  • “<=” means “is less than, or equal”
  • “!=” means “is not equal to”

The “NOT” operator

In working with boolean expressions (those formulas that end up giving “true” or “false” results), we can use the “NOT” operator to flip them around. “not true” is false!

Most languages also provide a “NOT” operator. In c++ the operator is the exclamation point, so this works:

  • “!(a > b)” means “is ‘a’ less than or equal to ‘b’?”

Do you see why? If “a > b” is false, then it must be that “a is less than or equal to b”. That is the opposite of “>”, not just “a < b”. What if they are equal?

In any case, using the “not” operator (“!”) turns the answer around. Why use these is up to you to decide. I seldom make my questions weird, preferring to make the question as clear as I can!

More Complex Questions

We often want to ask more complex questions.

The AND Logical Operator

A common question asks is a number falls between two values:

  • Is A between 5 and 10?

Here is a C++ expression that might do the job:

  • (A > 5) && (A < 10)

Note

I am using parentheses to avoid confusion here. The expression would work fine without those, but we need to study expressions more to see why.

Notice I used a weird operator: “&&”. Read this operator as “and”, a logical operator.

That means this expression is equivalent to this sentence:

  • “A is greater than 5, and A is less than 10”

That sentence is either “true” or “false”.

Does it do the job? That depends on if the values 5 and 10 are allowed. In the expression above, ‘A’ cannot take on either of these values. If you meant for those to be included as legal values, you should have written this:

  • (A >= 5) && (A <= 10)

There is another logical operator we can use:

The OR Logical Operator

What values for “A” could we have to make the following question “true”?

  • “A is greater than 5, or A is less than 10”

Think about it. Is a value of -100 greater than 5? No? Is it less than 10? It is! The logical operator we used here is “OR”, meaning either part can be “true” to give a true result. So this boolean expression is “true” for any value of “A”. Probably not what we wanted!

In C++, the expression would look like this:

  • (A >= 5) || (A <= 10)

It still is not a good expression, and might be a mistake! Beginners often make this mistake when building their first logical expressions!

This expression would be OK, though:

  • (A > 10) || (A < 5)

This expression will evaluate to “false” for any value between 5 and 10, inclusive! It will be “true” for any other values.

That is enough of an introduction to logical expressions to get you started. Let’s take a last look at our sample program:

Is Our Program Complete?

Left unsaid in this program is the fact that turning on the heat will make the temperature go up, and turning on the air conditioner will make the temperature go down.

Study this and see if you think it will do the job. (It won’t, by the way!) Can you make out what will happen, even though you do not know anything about

There are a few modules included here that are not shown, and those deal with reading the stuff from our human world. We test to see if a button has been pressed and use that to increase or decrease the current temperature setting.

Make sure you see the problem with this logic. It should come to you with a bit of thought. You should also see a simple solution to the problem with a bit more thought. If you do not see it, email me and I will tell you what I see!