Computer Science C++
In this assignment, you will write one class and a function that will convert an infix expression to an equivalent postfix expression. You will not write a
main() routine. One will be supplied for you and it will call your conversion function.
1. Initial Setup
- Log in to Unix.
- Run the
setupscript for Assignment 7 by typing:
2. Files We Give You
When you run the setup command, you will will get four files: the usual
inpost_main.cpp, which is the main routine that calls your functions; a sample input file called
infix.in; and the correct output generated by that input file,
Once again, use
diff to verify that your output matches that found in
3. Files You Must Write
You will write the following files:
mystack.h- contains the class definition for the
mystack.cpp- contains the definitions for member functions of the
inpost.cpp- contains your
inpost.h- contains the function prototype for
convert()so that the
main()can call it.
Each of the files (with the exception of
inpost.h) is described in more detail below. All header files should contain header guards to prevent them from being included multiple times in the same source file.
mystack class represents a stack of characters implemented as an array. This stack will be used by the algorithm that converts an infix string to a postfix string.
Like the other classes we've written this semester, this class should be implemented as two separate files. The class definition should be placed in a header file called
mystack class should contain the following
private data members:
- a pointer to an
char. I'll refer to this data member as the stack array pointer. It will be used to dynamically allocate an array of
char(the stack array).
size_tvariable used to keep track of the number of elements in the stack array. I'll refer to this data member as the stack capacity.
size_tvariable used to track the number of values current stored in the stack array. I'll refer to this data member as the stack size. The stack size must always be less than or equal to the stack capacity. Unless the stack is empty, the top item in the stack is always located in the stack array at location (stack size - 1).
The data type
size_t is defined in several header files, including
In addition to the data members described above, your class definition will need prototypes for the public member functions described below.
The definitions for the member functions of the class should be placed in a separate source code file called
mystack.cpp. Make sure to
#include "mystack.h" at the top of this file.
mystack class should have the following member functionss (most of which are quite small):
- This "default" constructor for the
mystackclass should initialize a new
mystackobject to an empty stack. When the function ends:
- The stack size for the new object should be 0.
- The stack capacity for the new object should be 0.
- The stack array pointer should be
mystack::mystack(const mystack& x)
- This "copy constructor" for the
mystackclass should initialize a new
mystackobject to the same string as the existing
x. When the function ends:
- The stack size for the new object should be equal to the stack size of the object
- The stack capacity for the new object should be equal to the stack capacity of the object
- If the stack capacity is 0, the stack array pointer for the new object should be
nullptr. Otherwise, the stack array pointer should point to an array of
charwith a number of elements equal to the stack capacity. The array should contain the same values as the stack array of the object
x. The contents of any array elements that are not actually part of the stack are unimportant.
- The destructor should delete the stack array.
mystack& mystack::operator=(const mystack& x)
- This overloaded copy assignment operator should assign one
mystackobject (the object
x) to another (the object that called the member function, which is pointed to by
this). The state of the data members when the function ends should be same as described above for the copy constructor.
size_t mystack::capacity() const
- This member function should return the stack capacity.
size_t mystack::size() const
- This member function should return the stack size.
bool mystack::empty() const
- This member function should return
trueif the stack size is 0. Otherwise, it should return
- This member function should set the stack size back to 0.
void mystack::reserve(size_t n)
- This member function modifies an object's stack capacity without changing the stack size or the contents of the stack array. The required logic is:
nis less than the stack size or
nis equal to the current stack capacity, simply return.
- Set the stack capacity to
- Declare a temporary array pointer (a pointer to an
- Use the temporary array pointer to dynamically allocate an array of
char. The number of elements in the new temporary array should be equal to the stack capacity.
- Copy the contents of the stack array into the temporary array.
- Delete the stack array.
- Set the stack array pointer to the temporary array pointer.
const char& mystack::top() const
- This member function should return the top item in the stack. You may assume this function will not be called if the stack is empty.
void mystack::push(char value)
- This member function should push the character
valueonto the top of the stack. The required logic is:
- If the stack size is equal to the stack capacity, the
reserve()function will need to be called to increase the stack's capacity. If the current capacity is 0, the capacity should be increased to 1. Otherwise, the current capacity should be doubled.
valueinto the stack array as the new top item in the stack.
- Increase the stack size by 1.
- This member function should pop the top item off of the stack by decreasing the stack size by 1. You may assume this function will not be called if the stack is empty.
Some of the member functions of the
mystack class will not be used in Assignment 7. However, you are still required to write them, and you should expect to lose points if they do not work correctly. Thoroughly testing the member functions of this class to make sure that they work is your responsibility.
This file should contain a definition for the following function:
string convert(const string& infix)
This function converts the infix expression passed to it as a C++ string into an equivalent postfix expression stored in a string object. You may assume that
infix is a valid expression, that only
')' will be used (i.e., no
'' will appear in the expression), that all variables will be single characters always in lower case, and that all constants will be integers.
The operators used, in order of precedence from highest to lowest, are
~(unary negation) and
Your function must take the expression in infix (which is a C++ string that may contain unnecessary whitespace and/or parentheses) and convert it to a postfix string stored in a
mystring object. It is very important that the postfix expression does not contain any leading or trailing whitespace and that the operators/operands are separated by exactly one space.
Infix to postfix conversion algorithm
Here is a description of the logic for the infix to postfix conversion using a stack.
opstackbe a stack used to hold operators during conversion.
infixbe a string containing the infix (input) expression tokens.
postfixbe a string where a postfix (output) expression will be constructed.
To convert the infix expression to a postfix expression:
Scan the infix string from left to right, extracting and processing one token at a time, skipping over whitespace:
- If the token is an operand, append it to the postfix string.
- If the token is a left parenthesis
'(', push it on the
- If the token is a right parenthesis
')', pop the
opstackuntil the corresponding left parenthesis is removed. Append each operator popped to the end of the postfix string and discard the
- If the token is an operator then, first, pop all operators from
opstackand append them to the postfix string until either a)
opstackis empty or b) the operator on
opstackhas a lower precedence than the new operator token. Then push the new operator token into
When the end of the infix string is encountered, pop and append all remaining operators from
opstack and append them to the postfix string.
The only output from this program is generated by the main routine supplied for you in
The following is a sample of what the given main() function will output when you run your finished program.
infix: ( d +1) *2 postfix: d 1 + 2 * infix: a-e-a postfix: a e - a - infix: (a-e-a)/( ~d + 1) postfix: a e - a - d ~ 1 + / infix: (a^2 + ~b ^ 2) * (5 - c) postfix: a 2 ^ b ~ 2 ^ + 5 c - * infix: ~ 3*~(a+1)- b/c^2 postfix: 3 ~ a 1 + ~ * b c 2 ^ / - infix: 246 + b /123 postfix: 246 b 123 / + infix: ( 246+(( b /123) ) ) postfix: 246 b 123 / +
- Start by writing the
mystackclass, making sure to test it thoroughly. As with the
matrixclass from Assignment 6, you should write the member functions for this class incrementally, building and testing as you go.
mystackclass is extremely similar in terms of its memory management to the
Vectorclass used as an example in the notes on dynamic storage allocation, so you can use that as your model when writing the destructor, copy constructor, and copy assignment operator. The logic for the various member functions of the class is also identical to what's outlined in the notes on array-based stacks.
- Save the
convert()function for last. You may want to make a copy of
infix.inand modify it to only include a few simple infix expressions at first, adding more as you proceed.
- You may want to write a function that takes a character operator and returns an integer precedence for that operator. This can be done using a simple
switchstatement or something more sophisticated. The precedence of a left parenthesis character
'('should be less than that of any of the operators.
- If you look at the algorithm to convert infix to postfix you will note that you never use the stack to store operands (variables or constants). You only use the stack to store operators or
'(', which are always single characters.
- The way the
mystackclass works, the operation "pop the stack and append what was popped to the postfix string" will actually require three steps: 1) call
top()to get the top character from the stack, 2) append that character to the postfix string (adding a space separator as needed), and 3) call
pop()to remove the top character from the stack.
- In processing the infix string, you may find it useful to use the standard library functions
islower(), which are declared in the header file
- It is also worth familiarizing yourself with the member functions of the C++
stringclass. For example, there are several member functions for appending to a string that might be very useful on this assignment.
Get Help With a similar task to - Computer Science C++
Tutlance Experts offer help in a wide range of topics. Here are some of our top services:
- Math homework help
- Nursing homework help
- Statistics homework help
- Nursing coursework help
- Capstone project writing services
- Essay writers for hire
- Case study writing help
- Buy college papers online
- Buy college research papers
- College homework help
- Professional resume writing services
- Programming homework help
- Coursework writing help
- Term paper writing help
- Biology homework help
- Do my physics homework
- Dissertation data analysis help
- PhD Dissertation writing services
- Chemistry homework help
Post your project now for free and watch professional experts outbid each other in just a few minutes.