In this homework assignment, you are supposed to implement a program for manipulating algebraic expressions of infix and prefix forms. Your implementation should enable the user to convert an expression of infix form to prefix form as well as to evaluate prefix expressions.
Your implementation MUST include the following global functions whose details are given below. Note that we will use these function prototypes to test your programs. Thus, you are not allowed to change the prototypes of these functions. On the other hand, you are free to add as many additional functions as you would like into your implementation.
// It converts an infix expression exp to its equivalent prefix form.
string infix2prefix( const string exp );
// It evaluates a prefix expression.
double evaluatePrefix( const string exp );
You MUST use stacks in your implementation. Thus, you will define a class for the ADT stack and use it in your functions. Note that you are allowed to use the C++ codes that are given in your textbook.
In your algorithms, you may have the following assumptions:
1. The input strings are syntactically correct expressions. For example, you may assume that the string is a valid infix expression when the infix2prefix function is called or you may assume that the string is a valid prefix expression when the evaluatePrefix function is called.
2. An input string can include only digits and binary operators. You may assume that only the binary operators *, /, +, and - are allowed (no unary and exponentiation operators are allowed). Moreover, you may assume that operands are single digits (digits from 1 to 9). In case of infix expressions, the string can also include parentheses in addition to digits and binary operators. For simplicity, you may assume that there are no spaces between the digits and the operators.
Here is an example test program that uses these functions. We will use a similar (but different) program to test your solution so make sure that you test your solutions thoroughly.
#include "AlgebraicExpression.h"
int main() {
cout << infix2prefix("(4+5)-2*4") << endl;
cout << evaluatePrefix("/4+3*-528") << endl;
return 0; }
Notes:
1. In this assignment, you must have separate interface and implementation files (i.e., separate .h and .cpp files). We will test your implementation by writing our own driver .cpp file which will include your header files. For this reason, your files' names MUST BE "Stack.h", Stack.cpp, AlgebraicExpression.h and AlgebraicExpression.cpp. You should upload these files (and any additional files you may have in your solution) as a single zip archive file. The submissions that do not obey these rules will not be graded. You must also write your own driver file, which must be different from the one that we gave above, to test each of your functions. You MUST submit this test code as well in the archive file.
2. You MUST use the ADT stack in your implementation. Thus, you will define and implement a class for the ADT stack and use it in your functions. Note that you are allowed to use the C++ codes that are given in your textbook but are not allowed to use any other stack implementation. For example, you cannot use the stack class defined in another book or on a web site. Similarly, you are not allowed to use any functions in the C++ standard template library (STL).
3. Your code must not have any memory leaks. You will lose points if you have memory leaks in your program even though the outputs of the operations are correct.