Software Development: Data Structures and Performance (SCQF Level 8)HL9T 3
Outcomes 2 and 3
Pass Fail Remediation
Outcomes 2 and 3
For Outcomes 2 and 3 you are required to implement a small application using at least two different data structures. Each data structure and the algorithms operating on it must be accurately documented and tested. The application itself must also be accurately documented and tested.
The application that you are required to construct is a system that converts infix notation of arithmetic expressions into the equivalent postfix notion. This can be performed by implementing Dijkstra’s shunting yard algorithm.
Your system must:
Accept an infix arithmetic expression as a string.
Tokenise the string
Rearrange the tokens into a queue of tokens in postfix order
For this task your systems must recognise and appropriately process the following symbols
0-9 ( operands )
+ – * / ( add, subtract, multiply and divide )
( and ) ( open and close parenthesis )
You are not required to deal with floating point numbers, so the . ( decimal point ) symbol need not appear or be processed. ( If candidates chose to include this it must be correctly processed )
The application must be implemented as two different data structures, with parameterised functions correctly implementing all of the functionality, such as init(), isFull(), isEmpty() add() and remove()
It is not a requirement of this application that it performs the expression evaluation.
Listings, documentation and test results for the two data structures used.
Listing, documentation and test results for the application.
You are required to complete this work without assistance so that your assessor may require you to discuss your submission to ensure authenticity. You may refer to your notes and online help throughout the assessment.