[SOLVED] Java algorithm Assign4V0

Assign4V0

COMP2150Assignment4Winter2017

1

Due:

April21,2017,before11:59pm.

Notes

PleasefollowboththeProgrammingStandardsandAssignmentGuidelinesfor
allworkyousubmit.Programmingstandards1-25areineffect.

Hand-inwillbeviatheD2LDropboxfacility.Makesureyouleaveenoughtime
beforethedeadlinetoensureyourhand-inworksproperly.

Allassignmentsinthiscoursecarryanequalweight.

Question1:IntroductiontoRuby
InthefirstpartofthisquestionyouwillimplementaStackandaQueue(aslinked
structures)inaRubymodule.Youwillthenusethemoduletomakeasimplecalculator.

PartA:A4DataStructures.rb

ImplementtheA4DataStructuresmoduleasdescribedbelow.

TheNodeclassisastandardsingly-linkedNode.Theinitialize()methodmustaccept0,1or
2parameters(if1isprovided,useittoinitializethedata;if2areprovided,initializethe
dataandlink).Provideato_s()methodwhichreturnsastringrepresentationofthedata
item.HaveRubyautomaticallygenerateanynecessarygetters/setters
(accessors/mutators).

TheAbstractListclassimplementsastandardsingly-linkedlist.Itmustbeabstractinthe
sensethatyoushouldpreventitfrombeinginstantiated.Itmustsupportthefollowing
methods:insertFront(item),insertBack(item),removeFront(),empty?()andto_s().(The
to_smethodmaybeusefulindebuggingyourprogram.)TheinsertFront,insertBackand
removeFrontmethodsmusthaveprotectedvisibility(howdoesthisdifferfromJavas
versionofprotected?).
TheStackclassextendsAbstractListtoimplementabasicstackwithpush(item),pop(),
andtop()methods.TheQueueclassextendsAbstractListtoimplementabasicqueuewith
enqueue(item)anddequeue()methods.
Theselasttwoclassesareexamplesoflimitation.Howareyouhidingtheunderlying
methodsofAbstractListfrombeingaccessed?

PartB:A4Calculator.rb

ThisprogramwillmakeuseofthemoduleyoucreatedinPartAtoevaluatesimpleinteger
expressions,e.g.(2+3)*4.
Theexpressionsarelimitedtothefollowing:
Singledigit,unsignedintegers,i.e.09.Signednumbersarenotallowed.Howeveryoucould

createlargernumbersornegativenumbersusingarithmetic(e.g.4*5,0-1).

COMP2150Assignment4Winter2017

2

Thefivebasicoperators,+,-,*,/and%.
Parentheses,(and).
Blanks,whichareignored.
Theexpressionswillbereadfromstandardinput,oneperline(Youcanuse
line=$stdin.readline).Processingwillcontinueuntilablanklineisentered.Youcan
assumethatalltheexpressionsarevalid,infixexpressions(i.e.theoperatorisbetween
theleftandrightoperands).
Evaluationisdoneintwosteps:

1. Converttheinfixexpressionintotheequivalentpostfix(alsoknownasReversePolish
notation)expression.Apostfixexpressionplacestheoperatorafterthetwooperands(e.g.2
3+).

2. Evaluatethepostfixexpression.Postfixexpressionscontainnobracketsandevaluationis
straightforwardusinganevaluationstack.

Conversionofinfixexpressionstopostfixemploysbothaqueue(toholdtheresulting
postfixexpression)andastack(totemporarilyholdoperators).Itisknownasthe
Railroadalgorithm,becauseindiagramstheoperatorstackisshownasasidetrackfor
shuntingoperatorsbeforemovingthemtotheoutput.

Tousetherailroadalgorithm,weassignprioritylevelstotheoperators,andtotheleft
parenthesis,asfollows:

Multiplicativeoperators(*,/,%):2
Additiveoperators(+,-):1
Leftparenthesis(:0

Weusetheprioritylevelstodecidewhentostoreanoperator,andwhentocopyittothe
outputpostfixexpression.Hereisapseudo-codedescriptionoftheconversionmethod.
Writingapriority()methodwouldbehelpful.

convertToPostfix (infix){
Queue postfix = new Queue()
Stack opStack = new Stack()
for (each character c in infix)
if (c is a blank) discard
else if (c is a digit) postfix.add(c)
else if (c is () opStack.push(c)
else if (c is ))
while (opStack.top != () postfix.add(opStack.pop)
opStack.pop// discard the (
else// c is an operator
while !opStack.isEmpty && prio(c) <= prio(opStack.top) postfix.add(opStack.pop) opStack.push(c) // end of for loop COMP2150Assignment4Winter20173 pop remaining operators in opStack and add to postfix return postfix }// convertToPostfix Intheresultingpostfixexpression,theparenthesesfromtheinfixexpressionhavebeendiscarded,thedigitsareinthesameorderasintheinfixexpression,andtheoperatorswillbeorderedintheorderthattheywillbecarriedout.Forexample:infix: 2 * (3 + 4);postfix:2 3 4+ *.Theevaluationmethodissomewhatsimplerthantheconversionmethod.Itusesastacktostoreintermediateresultsintheevaluation.Whenthealgorithmfinishes,thereisasinglevalueleftonthestack,whichistheresultoftheexpressionitself.Hereisapseudo-codedescriptionoftheevaluationmethod.evaluate (postfix){ Stack evalStack = new Stack() while (!postfix.isEmpty) op = postfix.remove if (op is in ‘0’..’9′) convert to corresponding int and push onto evalStack else // it is an operator right = evalStack.pop left = evalStack.pop if(op is division or remainder) if(right is zero) error(“division by zero”) else result = left op right evalStack.push(result) // end of while loop return evalStack.top }// evaluate Whenevaluatingdivisionoperations(/or%)youmustcheckfordivisionbyzero.Notethatwhenpoppingoperandsoffthestack,therightoneispoppedfirst(Why?).Usetheevalmethodtoevaluatetheresult.Whendisplayingtheresultoftheevaluation,echotheoriginalinputandtheresult(e.g.(2 + 3) * 4 = 20)SubmissionSubmittwofiles(A4DataStructures.rbandA4Calculator.rb).SubmitallfilesonD2L.