Need to implement stack using array represenation in C++ from the description an

Question

Need to implement stack using array represenation in C++ from the description and complete both parts. I also pasted below the screenshow what code is in the "program.c" file.

Description: Part I: Implement stack using array representation Your program should support normal stack operations as learned from the class Part II: Make use of your own stack implementation (from Part I) to check any program for balanced symbols: .0.0 Example: t0;, 0);: legal (G, (O;: illegal Write your program using C++, it reads the string of symbols from a program file (e.g.. program.c) and print "legal" or "illegal" as the result.

Explanation / Answer

                                                PART I STACK USING ARRAY
Here simple explaination of stack using Array is given . Stack is a data structure which perform operations in a particular order. The order may be LIFO(Last In First Out) or FILO(First In Last Out).

basic operations performed By The stack :

   Push : used to Add item in the stack. If the stack is full, then it is said to be an Overflow condition     Pop   :   used to Remove item from the stack. The items are popped(remove) in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow.

   Peek or Top : this operation Returns top element of stack.
   isEmpty       : this operation Returns true if stack is empty, else false.

Complexities of operations on stack :

We do not run any loop in any of these operations hence push(), pop(), esEmpty() and peek() all take O(1) time.

Now we will see the Program implementaion in C++

/* this is C++ program to implement basic stack operations */

#include<bits/stdc++.h>
using namespace std;
#define MAX 1000
//preprocessor directives for our stack c++ program
class Stack
{
    int top;
public:
    int a[MAX];    // Maximum size of Stack is fixed as in preprocessor

    Stack() { top = -1; }

//top is initialise to -1 to check the emptyness of stack
    bool push(int x);
    int pop();
    bool isEmpty();
};

bool Stack::push(int x)
{
    if (top >= MAX)
    {
        cout << "Stack is full it Overflowing";
        return false;
    }
    else
    {
        a[++top] = x;
        return true;
    }
}

int Stack::pop()
{
    if (top < 0)
    {
        cout << "Stack is Underflowing";
        return 0;
    }
    else
    {
        int x = a[top--];
        return x;
    }
}
//function to check weither stack is empty or not
bool Stack::isEmpty()
{
    return (top < 0);
}

// main pogram to check our functions
int main()
{
    struct Stack s;
    s.push(20);
    s.push(89);
    s.push(50);

    cout << s.pop() << " is Popped from our Stack ";

    return 0;
}

                                                  PART II PROGRAM FOR BALANCED SYMBOLS

Algorithm to do program :
1) Create character/string stack S .
2)Travers the characters in string Given in input program.
a) If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
b) If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from stack and if the popped character is the matching starting bracket then fine print "legal" else parenthesis are not balanced.
3) After complete traversal, if there is some starting bracket left in stack then print “illegal”

C++ IMPLEMENTAION :-

#include<bits/stdc++.h>
//#include<iostream>
#include<string>
#include<fstream>
using namespace std;

// function to check if paranthesis are balanced
bool areParanthesisBalanced(char expr[])
{
   stack<char> s;
   char a, b, c;

   // Traversing the Expression
   for (int i=0; i<strlen(expr); i++)
   {
       if (expr[i]=='('||expr[i]=='['||expr[i]=='{')
       {
           // Push the element in the stack
           s.push(expr[i]);
       }
       else
       {
           switch (expr[i])
           {
           case ')':

               // Store the top element in a
               a = s.top();
               s.pop();
               if (a=='{'||a=='[')
                   cout<<"Not Balancedn";
               break;
           case '}':

               // Store the top element in b
               b = s.top();
               s.pop();
               if (b=='('||b=='[')
                   cout<<"Not Balancedn";
               break;
           case ']':

               // Store the top element in c
               c=s.top();
               s.pop();
               if (c=='('||c=='{')
                   cout<<"Not Balancedn";
               break;
           }
       }
   }

   // Check Empty Stack
   if (s.empty())
       return true;
   else
       return false;
}

size_t getFileSize( std::string fileName ) {
    std::ifstream file( fileName, std::ios::binary | std::ios::ate );
    size_t fileSize = file.tellg();
    file.close();

    return fileSize;
}

// Driver program to test above function
int main()
{
int sz;
   //char expr[]="{()}[]";
sz = getFileSize( std::string "program.c" )
string myArray[sz];
ifstream file("program.c");
    if(file.is_open())
    {

        for(int i = 0; i < sz; ++i)
        {
            file >> myArray[i];
        }
    }
   if(areParanthesisBalanced(myArray))
       cout<<"legal";
   else
       cout<<"illegal";
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.