## advanced placement computer science - C++

Lesson 8:  Structured Programming, Control Structures, if-else Statements, Pseudocode

Introduction:                 This lesson is the first of four covering the standard control structures of a high-level language.  Using such control structures requires the creation of simple to complex Boolean statements which evaluate to true or false.   After covering the relational and logical operators available in C++, the remainder of this lesson will present the if-else control structure.

Objectives: The key topics:

A.    Structured Programming                                        B.    Control Structures
C.    Algorithm Development and Pseudocode                D.    Relational Operators
E.    Logical Operators                                                F.    Precedence and Associativity of Operators
G.    The if-else Statements                                        H.    Compound Statements
I.     Nested if-else Statements                                    J.     Conditional Operator
K.   Boolean Identifiers

Vocabulary:

 algorithm An algorithm is a solution to a problem. A plan for action to solve a problem. boolean identifier Boolean statements evaluate to true or false and the identifier is set to either T or F. conditional operator An if-else statement uses the conditional operator which checks the condition being tested and takes action depending on the condition. Control structure Each control structure has one entrance point and one exit point and controls the statement actions of the program. compound statement compound statement consists of multiple statements. if-else Selection is the control structure which allows choice among different directions.  Two-way selection with an if-else structure iteration Iteration is a control structure which refers to looping. logical operator The three logical operators of programming are AND, OR, and NOT which makes decisions based on these conditions. pseudocode Pseudocode refers to a rough-draft outline of an answer, written in English-like terms. relational operator A relational operator is a binary operator which compares two values. selection Selection is the control structure which allows choice among different directions. sequence Instructions which are executed in a particular order (once, line-by-line). stepwise refinement Stepwise refinement is the process of gradually developing a more detailed description of an algorithm Structured programming Programming which follows a set of rules including: No goto statements are to be used in writing code. All programs can be written in terms of three control structures:  sequence, selection, and iteration. Each control structure has one entrance point and one exit point. Control structures may be stacked (sequenced) one after the other. Control structures may be nested inside other control structures.

Discussion:                          A.    Structured Programming

1.     Up to this point in your study of computer science and C++, you have created programs which used only sequential execution.  So far function main () consisted of a sequence of lines which are executed once, line-by-line.  As we add the power of loops and selection, we need to use these tools in a disciplined manner.

2.    In the early days of programming (1960's), the approach to writing software was relatively primitive and ineffective.  Much of the code was written with goto statements which transferred program control to another part of the code.  Tracing this type of code was an exercise in jumping from one spot to another, leaving behind a trail of lines similar to spaghetti.  The term "spaghetti code" comes from trying to trace code linked together with goto statements.

3.    The research of Bohm and Jacopini has led to the rules of structured programming.  Here are five tenets of structured programming.

a.     No goto statements are to be used in writing code.

b.     All programs can be written in terms of three control structures:  sequence, selection, and iteration.

c.     Each control structure has one entrance point and one exit point.  We will sometimes allow for multiple exit points from a control structure using the break statement.

d.    Control structures may be stacked (sequenced) one after the other.

e.     Control structures may be nested inside other control structures.

4.    The control structures of C++ encourage structured programming.  Staying within the guidelines of structured programming has led to great productivity gains in the field of software engineering.

B.    Control Structures

 See Handout H.A.8.2, Control Structures in C++. 1.    There are only three necessary control structures needed to write programs:  sequence, selection, and iteration.

2.    Sequence refers to the line-by-line execution as used in your programs so far.   The program enters the sequence, does each step, and exits the sequence.

3.    Selection is the control structure which allows choice among different directions.  C++ provides different levels of selection:

One-way selection with an if structure
Two-way selection with an if-else structure
Multiple selection with a switch structure

4.    Iteration refers to looping.  C++ provides three loop structures:

while loops
do-while loops
for loops

5.    Of the seven control structures, the if-else and while loop are the most flexible and powerful for problem-solving.  The other control structures have their place, but if-else and while are the most common control structures used in C++ code.

6.    The diagrams in H.A.8.2, Control Structures in C++, are flowcharts which describe the flow of program control.  A statement rectangle in any control structure can be a simple line or even another control structure.  A statement can also be a compound statement which consists of multiple statements.

C.    Algorithm Development and Pseudocode

1.    An algorithm is a solution to a problem.  Computer scientists are in the problem-solving business.  They use techniques of structured programming to develop solutions to problems.  Algorithms will range from the easier "finding the average of two numbers" to the more difficult "visiting all the subdirectories on a hard disk, searching for a file."

2.    A major task of the implementation stage is the conversion of rough designs into refined algorithms which can then be coded in the implementation language of choice.

3.    Pseudocode refers to a rough-draft outline of an answer, written in English-like terms.  We will probably use phrases and words which are close to programming languages, but avoid using any specific language.  Once the pseudocode has been developed, translation into code occurs more easily than if we had skipped this pseudocode stage.

4.    Stepwise refinement is the process of gradually developing a more detailed description of an algorithm.  Problem solving in computer science involves overall development of the sections of a program, expanding each section with more detail, later working out the individual steps of an algorithm using pseudocode, then finally writing a code solution.

 See Handout H.A.8.3, Pseudocode and Algorithm Development. 5.    The handout, H.A.8.3, Pseudocode and Algorithm Development, will present a thorough example of this process.  You should read this now.

D.    Relational Operators

1.    A relational operator is a binary operator which compares two values.  The following symbols are used in C++ as relational operators:

<     less than       >     greater than       <=   less than or equal to

>=   greater than or equal to

==   equal to                   !=    not equal to

2.    A relational operator is used to compare two values, resulting in a relational expression.  For example:

number > 16           'F' == grade        passing >= 60

3.    The result of a relational expression is a bool value, true or false.

4.    When character data is compared, the ASCII code values are used to determine the answer.  The following expressions result in the answers given:

'A' < 'B'       evaluates as true, (65 < 66)
'd' < 'a'        evaluates as false, (100 < 97)
't' < 'X'        evaluates as false,  (116 < 88)

In the last example, you must remember that upper case letters come first in the ASCII collating sequence;  the lower case letters follow after and consequently have larger ASCII values than do upper case ('A' = 65, 'a' = 97).

5.    A very common error is to use only one equal (=) sign for the equality comparison.  Here is a critical distinction:

number = 5             assignment operator
number == 5           equality operator

The problem with forgetting to use the equality operator (==) is that the compiler accepts (number = 5) as a valid statement, which also returns the value 5.  Any non-zero value is equivalent to true in C++.  The resulting if statement will probably be in error because it is always true.

if (number = 5)
... code, which will always be executed ...

6.    You are strongly encouraged to reverse the order of equality comparisons to avoid the error of the section above.

if (5 == number)     // this is a better way
... code ...

When comparing a literal value against a variable, always place the variable on the right hand side.  If you had coded

if (5 = number)
... code ...

the compiler would reject this statement and require you to fix it.

E.  Logical Operators

1.    The three logical operators of programming are AND, OR, and NOT.  These operators are represented by the following symbols in C++:

AND           &&
OR  ||            (two vertical bars)
NOT           !

2.    The and operator requires both operands (values) to be true for the result to be true.

T  and  T  =  true
T  and  F  =  false
F  and  T  =  false
F  and  F  =  false

3.    The following are C++ examples of using the && (and) operator.

( (2 < 3)  &&  (3.5 > 3.0) )             evaluates as true
( (1 == 0)  &&  (2 != 3) )                evaluates as false

The && operator performs short-circuit evaluation in C++.  If the first half of an && statement is false, the operator immediately returns false without evaluating the second half.

4.    The or operator requires only one operand (value) to be true for the result to be true.

T  or  T  =  true
T  or  F  =  true
F  or  T  =  true
F  or  F  =  false

5.    The following is a C++ example of using the || (or) operator.

( (2+3 < 10)  ||  (21 > 19) )              evaluates as true

The || operator also performs short-circuit evaluation in C++.  If the first half of an || statement is true, the operator immediately returns true without evaluating the second half.

6.    The ! operator is a unary operator which changes a Boolean value to its opposite.

! false = true
! true = false

F.    Precedence and Associativity of Operators

1.    Introducing two new sets of operators (relational and logical) adds to the complexity of operator precedence in C++.  An abbreviated precedence chart is included here.  The complete precedence chart was given in Handout H.A.4.2, Operator Precedence in C++.

Table 8-1    Precedence and Associativity of Operators

Operator           Associativity

!  unary -  ++  --            right to left

*  /  %   left to right

+  -        left to right

<  <=  >  >=      left to right

==  !=   left to right

&&       left to right

||            left to right

=  +=  -=  *=  /=           right to left

2.    Because the logical operators have low precedence in C++, parentheses are not needed to maintain the correct order of solving problems.  However, they can be used to make complex expressions more readable.

((2 + 3 < 10)  &&  (75 % 12 != 12))           {easier to read}
(2  +  3  <  10  &&  75  %  12  !=  12)        {harder to read}

G.    The if-else Statements

1.    The general syntax of the if-else statement is as follows:

if  (expression) statement1;
else  statement2;

2.    if statements may omit the else option which result in one-way selection.

if (expression)  statement;

If the expression is non-zero, statement is executed, otherwise nothing is executed.  The following flowchart illustrates the flow of control. 3.    The full if-else statement allows for two-way control.  If the value of the expression is true, statement1 is executed.  If the value of the expression equals false, the else option results in statement2 being executed.  The following flowchart from  handout, H.A.8.2, illustrates the flow of control. 4.    The expression being tested must always be placed in parentheses.  This is a common source of syntax errors.

5.    Note that a semicolon must be placed after statement1, if the else option is used.

H.    Compound Statements

1.    The statement executed in a control structure can be a block of statements, grouped together into a single compound statement.

2.    A compound statement is created by enclosing any number of single statements by braces as shown in the following example:

if (expression)
{
statement1;
statement2;
statement3;
}
else
{
statement4;
statement5;
statement6;
}

I.     Nested if-else Statements

1.    The statement inside of an if or else option can be another if-else statement.  Placing an if-else inside another is known as nested if-else constructions.  For example:

if (expression1)
if (expression2)
statement1;
else
statement2;
else
statement3;

2.    The else option will be paired with the nearest unpaired if.  Statement2 is the alternative action of the inner if, while statement3 is the alternative action of the outer if.

3.    The above example has three possible different outcomes as shown in the following chart:

expression 1      expression2       statement executed

true        true        statement1
true        false       statement2
false       true        statement3
false       false       statement3

4.    Caution must be shown when using else statements inside of nested if-else structures.  For example:

if (expression1)
if (expression2)
statement1;
else
statement2;

Indentation is ignored by the compiler, hence it will pair the else statement with the inner if.  If you want the else to get paired with the outer if as the indentation indicates, you need to add braces:

if (expression1)
{
if (expression2)
statement1;
}
else
statement2;

The braces allow the else statement to be paired with the outer if

5.    Another alternative to the example in Section 4. makes use of the && operator.  A pair of nested if statements can be coded as a single compound && statement.

if (expression1 && expression2)
statement1;
else
statement2;

6.    The most common and effective use of nested if-else statements is called an if-else chain.  See the following formatting styles:

Formatting style 1    Formatting style 2

 if (expression1)        statement1; else        if (expression2)                                                           statement2;        else                                                           if (expression3)                                                                                                            statement3;                                                           else                                                                                                            statement4; if (expression1)        statement1; else if (expression2)        statement2; else if (expression3)        statement3; else        statement4;

Notice that each successive if-else statement is buried deeper in the overall structure.  Statement4 will only be executed if the first three expressions are zero (false).

7.    Formatting style 1 lines up the if with its counterpart else keyword.  This makes it easy to check syntax but the indentation can get rather deep.  Formatting style 2 is a more compact version but you need to be careful about which else statement belongs to which if.  Formatting style 1 is more appropriate if the statements are compound statements.  Formatting style 2 is appropriate if the statements are single-line statements.

8.    The advantage of such an if-else chain is efficiency in execution.  If a non-zero value (true) is encountered at any level, that statement is executed and the rest of the structure is ignored.

9.    Consider the following example of determining the type of triangle given the three sides A, B, and C.

if ( (A  == B)  &&  (B == C) )
cout << "Equilateral triangle" << endl;
else  if ( (A == B)  ||  (B == C)  ||  (A == C) )
cout << "Isosceles triangle" << endl;
else
cout << "Scalene triangle" << endl;

If an equilateral triangle is encountered, the rest of the code is ignored.  Such a chain is best constructed by placing the most demanding case at the top and the least demanding case at the bottom.

J.     Conditional Operator  (optional)

1.    C++ provides an alternate method of coding an if-else statement using the conditional operator.  This operator is the only ternary operator in C++ as it requires three operands.  The general syntax is:

(condition) ? statement1 : statement2;

2.    If the condition is true, statement1 is executed.  If the condition is false, statement2 is executed.

3.    This is appropriate in situations where the conditions and statements are fairly compact.

int  max (int a, int b)     // returns the larger of two integers

{

(a > b)  ?  return a  :  return b;

}

K.   Boolean Identifiers

1.    The execution of if-else statements depends on the value of the Boolean expression.  We can use bool variables to write code which is easier to read.

2.    For example, the bool variable done could be used to write code which is more English-like.

Instead of

if (done == true)
cout << "We are done!" << endl;

we can write

if (done)
cout << "We are done!" << endl;

3.    Using Boolean identifiers with conditional loops allows a separation of solving expressions from thinking about program control.  Here is an example solution using the while control structure (to be covered in the next lesson), presented in a blend of C++ and pseudocode:

bool  done = false;

while (!done)
do some code which could change the value of done

4.    Where appropriate you are encouraged to use bool variables to aid in program flow and readability.

Summary/Review:          Control structures are a fundamental part of high level languages.   Fluency in any high level language only comes with practice.  You will need to practice control structures in C++ as well as all other aspects of the language.

Assignment:                     Lab Exercise, L.A.8.1, IRS

  Bohm, C., and G. Jacopini, "Flow Diagrams, Turing Machines, and Languages with Only Two Formation Rules, "Communications of the ACM, Vol. 9, No. 5, May 1966, pp. 336-371."