Reference no: EM133518836

Data Structures

Purpose - To measure the student's ability to implement and/or use one or more specialized containers (e.g., stacks and queues) to solve an underlying problem in C++.

Overview
This assignment will test your ability to implement a (linked) stack and queue as well as use their functionality to convert infix (mathematical) expressions to postfix. Infix notation is the typical expression format we encounter, where the operator is between the operands (e.g., A+B). In a postfix expression, the operator is written after the operands (e.g., AB+). Notably, due to their structure, postfix expressions do not require parentheses to specify the order of operations, making them ideal for digital evaluation of mathematical expressions!

The Supplied Files

This section gives an overview of the files that you are provided as part of this assignment, none of which you should modify. In contrast to Assignment 1, you are not provided with (skeleton) implementation files - you will be expected to create these files from scratch. You are recommended to take some time to understand the overall structure of the program before starting the implementation phase.

• main.cpp - contains the main function and the logic to present the prompt, call the converter, then display the results. This file should not be modified.

• empty_collection_exception.h - contains the definition of an exception that can be thrown when an operation is attempted on an empty stack or queue. Note: there is no accompanying .cpp file - the .h file contains the complete definition and implementation of the exception. This file should not be modified.

• lstack.h - contains the header for the LStack class, which includes the instance variables and behaviours that your stack should contain. This file should not be modified.

• lqueue.h - contains the header for the LQueue class, which includes the instance variables and behaviours that your queue should contain. This file should not be modified.

• infix_to_postfix_converter.h - contains the header for the infix_to_postfix_converter class, which includes the instance variables and behaviours that your converter class should contain. This file should not be modified.

• makefile - the makefile for the project, which outlines the build recipe. The -g flag is set for you to make debugging and/or memory leak detection more convenient, should you wish to use these tools. This file should not be modified.

Running the Program
Of course, you will need to ensure the program is compiled prior to running it. You can use the supplied makefile for this - it will produce an executable called Converter. The program should be executed as normal using the command:

./Converter

Note: the program will not compile as supplied, as you will not have the necessary implementation files. You are encouraged to write skeleton files, similar to those in Assignment 1, to allow compilation of an incomplete program - this will allow you to work incrementally.

When the program is executed, you will be presented with a prompt. The prompt will allow you to enter an infix expression, which the program will convert to postfix. If you enter quit at the prompt, the program will print Goodbye! and exit. Otherwise, both the infix and postfix expressions will be displayed. Figure 1 presents an example of the program execution and a few examples of expressions that have been converted. As with the first assignment, you are recommended to have a look through the code, particularly the header files, to better understand the requirements for the various methods you must write.

The Tasks
The first task is to implement templated stack and queue classes using a linked list as the underlying data collection. As the purpose of this assignment is to focus on the behaviour of the stack and queue data structures, you are expected to use std::list (std::list - cppreference.com) to provide the linked list behaviour. However, you are not permitted to use

std::stack or std::queue. This avoids being double penalised if your linked list did not work correctly in Assignment 1 and provides valuable experience working with an existing collection from the standard template library.

Next, you will implement the infix_to_postfix_converter class to convert an infix expression into an equivalent postfix expression. In our program, we will consider only a small set of binary operators, +, -, *, and /, along with parentheses. You can assume that the inputs to the program will be well-formed, infix expressions that may contain unsupported operators. You do not need to handle negative numbers and the symbol - should be interpreted as subtraction. An examples, the expression ‘A + B - C' would be converted to ‘AB+C-' (Note: spaces are removed in the conversion process) while ‘(A+B)*C-D' would be converted to ‘AB+C*D-'.

LStack

The LStack class is a templated version of a stack and should be implemented as discussed in lecture, noting that you are required to use (a pointer to) std::list as the underlying list. For a full list of methods required and some important details, you should examine the lstack.h file and its associated documentation.

LQueue

The LQueue class is a templated version of a queue and should be implemented as discussed in lecture, noting that you are required to use (a pointer to) std::list as the underlying list. For a full list of methods required and some important details, you should examine the lqueue.h file and its associated documentation.

infix_to_postfix_converter

The infix_to_postfix_converter class contains the main logic of the conversion process and uses your LStack and LQueue classes to supply the underlying functionality. That is, this class must use the public interface provided by your LStack and LQueue classes to perform the conversion process, as further detailed in the header file. For a full list of methods required and some important details, you should examine the infix_to_postfix_converter.h file and its associated documentation. You are not permitted to use std::stack or std::queue.

The Conversion Process
To illustrate the rules for conversion, assume that input is an infix expression, queue is a queue of characters (that will hold the postfix expression), and stack is stack of characters (that will temporarily hold operators during the conversion):

1. Ensure queue and stack are initialised.

2. While there are more characters: get the next symbol, sym, from input.

a. If sym is a space character, it can be ignored and should not be placed in the
queue.

b. If sym is an operand (i.e., a letter or number), enqueue sym to queue. Hint: The isalnum function (std::isalnum - cppreference.com), which returns true if a character is a number of letter, may be useful here!

c. If sym is ( , push sym to stack.

d. If sym is ), pop and enqueue all symbols from stack to queue until you encounter a left parenthesis. The left parenthesis should be popped and discarded, not placed into the queue.

e. If sym is an operator (i.e., +, -, *, or /):

i. Pop and enqueue all the operators from stack to queue that are above the most recent left parenthesis and have precedence greater than or equal to sym. Hint: while there are different ways you can address the left parentheses in the stack, you may find it useful to consider it as an operator with lower precedence than any of the other operators. In this way, you will always stop processing when you encounter the (left) parenthesis.

ii. Push sym onto stack.

f. If sym is any other character, throw an exception with an appropriate message. Note: you do not need to use a custom exception for this purpose. You may simply throw an existing option, such as std::invalid_argument with a suitable error message passed as the argument. For further information, see std::invalid_argument - cppreference.com.

3. After processing input, some operators might be left on the stack. Pop and enqueue everything from stack to queue.

4. Dequeue all characters from queue to build a string containing the postfix string.

Normal precedence rules apply for the operators, namely that * and / have equal priority, which is greater than the priority of + and - (which are also of equal priority). For example, you may consider the priority of * and / to be 2 and the priority of + and - to be 1. As above, you may also find it useful to consider a left parenthesis as an operator with precedence 0, though you may address this in a different way.

Figure 2 gives a visual example of the conversion process for the expression A+B*C-D. Note: you do not need to support x as multiplication - x should be interpreted as an operand.

Attachment:- Data Structures.rar