130 CHAPTER8. CONTROLSTRUCTURES,PART 2

a or (b and c) == (a or b) and (a or c)
a and (b or c) == (a and b) or (a and c)

A doublenegative cancelsout.

not(not a) == a

Thenexttwo identitiesareknownasDeMorgan’s laws.

not(a or b) == (nota) and (not b)
not(a and b) == (nota) or (not b)

Noticehow theoperatorchangesbetweenandandorwhenthenotis pushedintoanexpression.
OneapplicationofBooleanalgebrais theanalysisandsimplificationofBooleanexpressionsinsideof
programs.Forexample,let’s gobacktotheracquetballgameonemoretime.Above, wedevelopeda loop
conditionforcontinuingthegamethatlookedlike this:

while not (scoreA == 15 or scoreB== 15):

continue playing

Youcanreadthisconditionassomethinglike:Whileit is notthecasethatplayerA has 15 orplayerB has15,
continueplaying. We’reprettysurethat’s correct,but negatingcomplex conditionslike thiscanbesomewhat
awkward,tosaytheleast.Usinga littleBooleanalgebra,wecantransformthisresult.
ApplyingDeMorgan’s law, weknow thattheexpressionis equivalenttothis.

(not scoreA == 15) and (not scoreB == 15)

Remember, wehave tochangetheortoandwhen“distributing”thenot. Thisconditionis nobetterthan
thefirst,butwecangoonestepfartherbypushingthenots intotheconditionsthemselves.

while scoreA != 15 andscoreB != 15:

continue playing

Now wehave a versionthatis mucheasierto understand.ThisreadssimplyaswhileplayerA hasnotreached
15 andplayerB hasnotreached15,continueplaying.
Thisparticularexampleillustratesa generallyusefulapproachtoloopconditions.Sometimesit’s easier
tofigureoutwhena loopshouldstop,ratherthanwhentheloopshouldcontinue.Inthatcase,simplywrite
theloopterminationconditionandthenputanotinfrontofit.Anapplicationortwo ofDeMorgan’s laws
canthengetyoutoa simplerbutequivalentversionsuitableforuseinawhilestatement.

8.5 OtherCommonStructures

Takentogether, thedecisionstructure(if) alongwitha pre-testloop(while) providea completesetof
controlstructures.Thismeansthateveryalgorithmcanbeexpressedusingjustthese.Onceyou’ve mastered
thewhileandtheif, thereisnoalgorithmthatyoucannotwrite,inprinciple. However, forcertain
kindsofproblems,alternative structurescansometimesbeconvenient.Thissectionoutlinessomeofthose
alternatives.

8.5.1 Post-TestLoop

Supposeyouarewritinganinputalgorithmthatis supposedtogeta nonnegative numberfromtheuser. If the
usertypesanincorrectinput,theprogramasksforanothervalue.It continuesto repromptuntiltheuserenters
a validvalue.Thisprocessis calledinputvalidation. Well-engineeredprogramsvalidateinputswhenever
possible.
Hereis a simplealgorithm.

repeat
get a number fromthe user
until number is >= 0