[SOLVED] 程序代写代做代考 Java algorithm Assign4V0

Assign4V0

COMP2150Assignment4Winter2017

1

Due:

April21,2017,before11:59pm.

Notes

• Pleasefollowboththe“ProgrammingStandards”and“AssignmentGuidelines”for
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).

TheAbstractListclassimplementsa‘standard’singly-linkedlist.Itmustbe‘abstract’inthe
sensethatyoushouldpreventitfrombeinginstantiated.Itmustsupportthefollowing
methods:insertFront(item),insertBack(item),removeFront(),empty?()andto_s().(The
to_smethodmaybeusefulindebuggingyourprogram.)TheinsertFront,insertBackand
removeFrontmethodsmusthaveprotectedvisibility(howdoesthisdifferfromJava’s
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.0…9.Signednumbersarenotallowed.Howeveryoucould

‘create’largernumbersornegativenumbersusingarithmetic(e.g.4*5,0-1).

COMP2150Assignment4Winter2017

2

• Thefive‘basic’operators,+,-,*,/and%.
• Parentheses,‘(‘and‘)’.
• Blanks,whichareignored.
Theexpressionswillbereadfromstandardinput,oneperline(Youcanuse
line=$stdin.readline).Processingwillcontinueuntilablanklineisentered.Youcan
assumethatalltheexpressionsarevalid,“infix”expressions(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
“Railroad”algorithm,becauseindiagramstheoperatorstackisshownasa“sidetrack”for
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.