Question

You will write the following files:

• mystack.h - contains the class definition for the mystack class.
• mystack.cpp - contains the definitions for member functions of the mystack class.
• inpost.cpp - contains your convert() function.
• 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.

3.1. The mystack class

The 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.h.

Data Members

The 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).
• a size_t variable used to keep track of the number of elements in the stack array. I'll refer to this data member as the stack capacity.
• a size_t variable 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 <cstddef> and <cstdlib>.

In addition to the data members described above, your class definition will need prototypes for the public member functions described below.

Member Functions

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.

The mystack class should have the following member functionss (most of which are quite small):

• mystack::mystack()

  This "default" constructor for the mystack class should initialize a new mystack object 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 nullptr.

• mystack::mystack(const mystack& x)

  This "copy constructor" for the mystack class should initialize a new mystack object to the same string as the existing mystack object x. When the function ends:

  • The stack size for the new object should be equal to the stack size of the object x.
  • The stack capacity for the new object should be equal to the stack capacity of the object x.
  • 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 char with 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.

• mystack::~mystack()

  The destructor should delete the stack array.

• mystack& mystack::operator=(const mystack& x)

  This overloaded copy assignment operator should assign one mystack object (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 true if the stack size is 0. Otherwise, it should return false.

• void mystack::clear()

  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:

  • If n is less than the stack size or n is equal to the current stack capacity, simply return.
  • Set the stack capacity to n.
  • Declare a temporary array pointer (a pointer to an char).
  • 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 value onto 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.
  • Copy value into the stack array as the new top item in the stack.
  • Increase the stack size by 1.

• void mystack::pop()

  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.

Important Point

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.

3.2. inpost.cpp

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 '(' and ')' will be used (i.e., no '{}' or '[]' 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

1. ~ (unary negation) and ^ (exponentiation)
2. * (multiplication) and / (division)
3. + (addition) and - (subtraction)

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.

• Let opstack be a stack used to hold operators during conversion.
• Let infix be a string containing the infix (input) expression tokens.
• Let postfix be 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 opstack.
• If the token is a right parenthesis ')', pop the opstack until the corresponding left parenthesis is removed. Append each operator popped to the end of the postfix string and discard the '(' and ')' parenthesis tokens.
• If the token is an operator then, first, pop all operators from opstack and append them to the postfix string until either a) opstack is empty or b) the operator on opstack has a lower precedence than the new operator token. Then push the new operator token into opstack.

When the end of the infix string is encountered, pop and append all remaining operators from opstack and append them to the postfix string.

4. Output

The only output from this program is generated by the main routine supplied for you in inpost_main.cpp.

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 / +

Answer 1

Program:

mystack.h

#ifndef MYSTACK_H
#define MYSTACK_H

#include<cstdlib>

class mystack
{
private:
char *stk;
size_t stackCapacity;
size_t stackSize;
public:
mystack();
mystack(const mystack& x);
~mystack();
mystack& operator=(const mystack& x);
size_t capacity() const;
size_t size() const;
bool empty() const;
void clear();
void reserve(size_t n);
const char& top() const;
void push(char value);
void pop();
};

#endif // MYSTACK_H

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

mystack.cpp

#include"mystack.h"

//default" constructor
mystack::mystack()
{
stackSize = 0;
stackCapacity = 0;
stk = nullptr;
}

//copy constructor
mystack::mystack(const mystack& x)
{
stackCapacity = x.stackCapacity;
stackSize = x.stackSize;
stk = new char[stackCapacity];
}

//destructor
mystack::~mystack()
{
delete stk;
}

//overloaded copy assignment operator
mystack& mystack::operator=(const mystack& x)
{
stackCapacity = x.stackCapacity;
stackSize = x.stackSize;
stk = new char[stackCapacity];
return *this;
}

//function return the stack capacity
size_t mystack::capacity() const
{
return stackCapacity;
}

//function return the stack size
size_t mystack::size() const
{
return stackSize;
}

//function return true if the stack size is 0 Otherwise, return false.
bool mystack::empty() const
{
if(stackSize==0) return true;
return false;
}

//function set the stack size back to 0.
void mystack::clear()
{
stackSize = 0;
}

//function modifies an object's stack capacity
void mystack::reserve(size_t n)
{
if(n<stackSize || n==stackCapacity)
return;

stackCapacity = n;
char *tmp = new char[n];
for(int i=0; stackSize; i++)
{
tmp[i] = stk[i];
}

delete stk;
stk = tmp;
}

//function return the top item in the stack
const char& mystack::top() const
{
const char &c = stk[stackSize-1];
return c;
}

//function push the character value onto the top of the stack
void mystack::push(char value)
{
if(stackSize==stackCapacity || stackCapacity==0) stackCapacity++;
else stackCapacity+=2;
stk[stackSize] = value;
stackSize++;
}

//function pop the top item off of the stack by decreasing the stack size by 1
void mystack::pop()
{
stackSize--;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

inpost.h

#ifndef INPOST_H
#define INPOST_H

#include <iostream>
using namespace std;

string convert(const string& infix);
int precedence(char x);

#endif // INPOST_H

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

inpost.cpp

#include"inpost.h"
#include"mystack.h"

string convert(const string& infix)
{
mystack stack;
stack.reserve(10);
stack.push('(');

string output = "";
int n = infix.size();

for(int i=0; i<n; i++)
   {
   char ch = infix[i];
       if(isalnum(ch))
       {
           output = output + ch;
       }
       else if(ch=='(')
       {
           stack.push('(');
       }
       else if(ch==')')
       {
           while(stack.top()!='(')
           {
           output = output + stack.top();
           stack.pop();
           }
           stack.pop();
       }
       else
       {
       int p1=precedence(ch);
       int p2=precedence(stack.top());

       while(p1<=p2)
       {
           output = output + stack.top();
           stack.pop();
           p2=precedence(stack.top());
       }
       stack.push(ch);
       }
   }

   while(stack.top()!='(')
   {
       output = output + stack.top();
       stack.pop();
   }

   return output;
}

int precedence(char x)
{
   switch(x)
   {
       case '(':
           return 0;

       case '+':
       case '-':
           return 1;

       case '*':
       case '/':
           return 2;

       case '^':
case '~':
           return 3;

       default : return 999;
   }
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

main.cpp

#include <iostream>
#include"inpost.h"
#include"mystack.h"

using namespace std;

//main function

int main()
{
string s = "(d+1)*2";
string t = convert(s);

cout<<"Infix: "<<s<<endl;
cout<<"Postfix: "<<t<<endl;

s = "a-e-a";
t = convert(s);

cout<<"Infix: "<<s<<endl;
cout<<"Postfix: "<<t<<endl;

s = "(a-e-a)/(~d + 1)";
t = convert(s);

cout<<"Infix: "<<s<<endl;
cout<<"Postfix: "<<t<<endl;

return 0;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Output:

Infix: (d+1)*2
Postfix: d1+2*
Infix: a-e-a
Postfix: ae-a-
Infix: (a-e-a)/(~d + 1)
Postfix: ae-a-d ~1 +/

N.B. Whether you face any problem then share with me in the comment section, I'll happy to help you.