Question

Using the code below from “LStack.h” file, write the code for a main program that takes as input an arithmetic expression. The program outputs whether the expression contains matching grouping symbols. For example, the arithmetic expressions { 25 + ( 3 – 6 ) * 8 } and 7 + 8 * 2 contains matching grouping symbols. However, the expression 5 + { ( 13 + 7 ) / 8 - 2 * 9 does not contain matching grouping symbols. There is a space between number / operator / grouping symbols. Just create “main2.cpp” for this problem. Do NOT make any changes to “LStack.h”. (25 points)

Hint: use “stoi()” library function for converting a string into an integer.

H FILE CODE

#ifndef LSTACK_TH
#define LSTACK_TH
#include <iostream>
using namespace std;

template < class dataType >
class Stack
{
public:
   Stack(); // create an empty stack
   Stack(const Stack<dataType>& original); // copy constructor
   ~Stack(); // destructor
   Stack& operator =(const Stack<dataType>& rightHandSide);
   void push(dataType dataVal); // add an element on top of the stack
   void pop(dataType& dataVal); // return the data at the top of the stack and then remove it
   void top(dataType& dataVal); // return the data at the top of the stack
   bool isEmpty() const; // return true if the stack is empty and false otherwise
private:
   struct StackNode
   {
       dataType data;
       StackNode* next;
   } *stackTop;

   //stackNode *stackTop;
};

// constructor
template < class dataType >
Stack<dataType> ::Stack() : stackTop(NULL)
{

}
//destructor ~Stack( )
template < class dataType >
Stack<dataType> :: ~Stack()
{
   StackNode* releasePtr; // to hold the address of the node to be removed
   while (stackTop != NULL)
   {
       releasePtr = stackTop;
       stackTop = stackTop->next;
       delete releasePtr;
   }
}
//copy constructor Stack( const Stack & original )
//Create a new stack object and initialize its elements with the elements of the original stack
template < class dataType >
Stack<dataType> ::Stack(const Stack<dataType>& original)
{
   if (original.stackTop == NULL) // original stack is empty
       stackTop = NULL;
   else
   {
       StackNode* from, // hold the address of the current node in the original stack
           * to; // hold the address of the new node of the new stack
               //create the first node of the new stack and copy the first node of the original stack to it
       to = new StackNode;
       to->data = original.stackTop->data;
       stackTop = to; // copy the first node
       //copy the rest of the nodes
       from = original.stackTop->next;
       while (from != NULL)
       {
           to->next = new StackNode; // create a new node and connect it to the current node
           to = to->next; // make the new node the current node
           to->data = from->data; // copy the data to the current node
           from = from->next; // make the next node in the original stack the current node
       }
       to->next = NULL;
   }
}
// overloaded assignment operator
// use of const return to avoid left associativity: (A = B) = C
// do not copy a stack into itself. First destroy the left hand side stack and create another one with the same number of nodes as the right hand side stack

template < class dataType >
Stack<dataType>& Stack<dataType> ::operator = (const Stack<dataType>& rightHandSide)
{
   if (this != &rightHandSide) // copy only if the two stacks are not the same
   {
       this -> ~Stack(); // destroy the left hand side stack
       if (rightHandSide.isEmpty()) // the right hand side stack is empty
           stackTop = NULL;
       else
       {
           StackNode* from, // hold the address of the current node in the right hand side stack
               * to; // hold the address of the new node of the left hand side stack
           //create the first node of the left hand side stack and copy the first node of the right hand side stack to it */
           to = new StackNode;
           to->data = rightHandSide.stackTop->data;
           stackTop = to; // copy the first node
           //copy the rest of the nodes
           from = rightHandSide.stackTop->next;
           while (from != NULL)
           {
               to->next = new StackNode; // create a new node and connect it to the current node
               to = to->next; // make the new node the current node
               to->data = from->data; // copy the data to the current node
               from = from->next;// make the next node in the right hand side stack the current node
           }
           to->next = NULL;
       }
   }
   return(*this);
}

//member function push( )
template < class dataType >
void Stack<dataType>::push(dataType dataVal)
{
   //add the element to the top of the stack
   StackNode* newptr = new StackNode;
   newptr->data = dataVal;
   newptr->next = stackTop;
   stackTop = newptr;
}
// member function isEmpty( )
template < class dataType >
bool Stack<dataType> ::isEmpty() const
{
   return(stackTop == NULL);
}
//member function top( )
//return the data at the top of the stack
template < class dataType >
void Stack<dataType> ::top(dataType& dataVal)
{
   if (stackTop == NULL) // the stack is empty
   {
       cerr << endl << "Stack is empty" << endl;
       exit(1);
   }
   dataVal = stackTop->data;
}
// member function pop
//return the data at the top of the stack and clear the top of the stack
template < class dataType >
void Stack<dataType> ::pop(dataType& dataVal)
{
   if (stackTop == NULL) // the stack is empty
   {
       cerr << endl << "Stack is empty" << endl;
       exit(1);
   }
   dataVal = stackTop->data; // return the data at the top of the stack
   StackNode* discardptr; // to hold the address of the node to be removed
   discardptr = stackTop;
   stackTop = stackTop->next; // set the top of the stack to the next node
   delete discardptr;
}

#endif

SAMPLE INPUT FOR MAIN FILE

Input:

Enter expression:

{ 25 + ( 3 – 6 ) * 8 }

Output:

Yes

Input:

Enter expression:

7 + 8 * 2

Output:

Yes

Input:

Enter expression:

5 + { ( 13 + 7 ) / 8 - 2 * 9

Output:

No

Input:

Enter expression:

( 5 + { ( 13 + 7 ) / 8 } – 2 ) * 9

Output:

Yes

Input:

Enter expression:

( 5 + { ( 13 + 7 ) } – 8 } – 2 ) * 9

Output:

No

Answer 1

Hello! :)

Here is the documented code to solve the assignment:

main2.cpp:

#include <iostream>
#include <sstream>

#include "LStack.h"

// To enumerate the grouping symbols.
enum class SYMBOL
{
    LBRACKET,
    LBRACE,
    LPAREN,
};

/**
 * Pops a symbol from the stack and checks if it matches the passed symbol.
 * @param stack Reference to a Stack<SYMBOL> instance.
 * @param symbolToMatch symbol to match the popped symbol against.
 * @return true if the popped symbol matches the passed argument, otherwise false.
 */
bool validate(Stack<SYMBOL>& stack, const SYMBOL symbolToMatch)
{
    bool status{true};

    if(stack.isEmpty())
    {
        // stack is empty
        status = false;
    }
    else
    {
        // popping from stack
        SYMBOL poppedSymbol;
        stack.pop(poppedSymbol);

        // checking for match
        if(poppedSymbol != symbolToMatch)
        {
            status = false;
        }
    }

    return status;
}

int main()
{
    // reading in the expression and creating a stringstream for easy parsing
    std::cout << "Enter expression:" << std::endl;
    std::string expression;
    getline(std::cin, expression);
    std::stringstream ss(expression);

    // check for matching grouping symbols
    bool status{true};
    Stack<SYMBOL> stack;
    std::string symbol;
    while(ss >> symbol and status)
    {
        // check for: []
        if(symbol == "[")
        {
            stack.push(SYMBOL::LBRACKET);
        }
        else if(symbol == "]")
        {
            status = validate(stack, SYMBOL::LBRACKET);
        }

        // check for: {}
        else if(symbol == "{")
        {
            stack.push(SYMBOL::LBRACE);
        }
        else if(symbol == "}")
        {
            status = validate(stack, SYMBOL::LBRACE);
        }

        // check for: ()
        else if(symbol == "(")
        {
            stack.push(SYMBOL::LPAREN);
        }
        else if(symbol == ")")
        {
            status = validate(stack, SYMBOL::LPAREN);
        }
    }

    // checks if any grouping symbols
    // are left in the stack
    if(not stack.isEmpty())
    {
        status = false;
    }

    // printing the status of the check
    std::cout << (status ? "Yes" : "No") << std::endl;

    return 0;
}

Here is a snapshot of a demo run:

Hope this helps! :)