Redundant Braces | Amazon | InterviewBit | Solution | C++

Problem :

Given a string A denoting an expression. It contains the following operators ’+’, ‘-‘, ‘*’, ‘/’.

Chech whether A has redundant braces or not.

Return 1 if A has redundant braces, else return 0.

Note: A will be always a valid expression.

Solution:

 int Solution::braces(string A) {

    // create a stack

    stack<char>s;

    

    // process string char by char

    int l  = A.length();

    for(int i =0;i<l;i++){

        char c = A[i];

        // if c is ( or operator or operand , we push in s

        if(c == '(' || (c >= 'a' && c<='z') || c == '+'||c=='-'||c=='*'||c=='/'){

            s.push(c);

        }

        else{

            // else 

        

        // pop unless we get opening bracket and check the length of popped elements

        // if it is > 1

        //else end processing and it is redundant

        

            // (a + b) -> 5

            

        int p = 0;

        

        while(s.empty() == false && s.top()!='('){

            p++;

            s.pop();

        }     

        s.pop();

        if(p>1)continue;

        else{

            return 1;

        }

    

    }

    

}

return 0;

}

Simplify Directory Path | InterviewBit | Microsoft | Solution | C++

Problem : 
Given a string A representing an absolute path for a file (Unix-style).

Return the string A after simplifying the absolute path.

Note:
Absolute path always begin with ’/’ ( root directory ).

Path will not have whitespace characters.

Solution :

string Solution::simplifyPath(string A) {

    int l = A.length();

    stack<string>s;

    

    string dir = "";

    

    string res;

    res.append("/");

    

    for(int i = 0;i<l;i++){

        

        dir = "";

        

        // ignore all slashes

        while( i < l && A[i]=='/')i++;  

        

        // store dirname in dir 

        while(i < l && A[i]!='/'){

            dir.push_back(A[i]);

            i++;

        }

        

        // dir  == .  , continue

        if(dir.compare(".") == 0)continue;

        

        // dir  == .. , pop() , only if stack is not empty

        

        else if(dir.compare("..") == 0){

            if(!s.empty()){

                s.pop();

            }

        }

        // if dir != "" then store the dirname in stack

        else if(dir != ""){

            s.push(dir);

        }

    }

    

    // stack s , reverse s => rs

    stack<string>rs;

    while(!s.empty()){

        string t = s.top();

        rs.push(t);

        s.pop();

    }

    

     

    

    

    

    // pop element rs and store it res

    

    while(!rs.empty()){

        string t = rs.top();

        if(rs.size() == 1){

            res.append(t);

        }else{

            res.append(t+"/");

        }

        rs.pop();

    }

    

    return res;

}

Balanced Parantheses! | InterviewBit | Amazon | Google

 

Problem : 

Given a string A consisting only of '(' and ')'.


You need to find whether parantheses in A is balanced or not ,if it is balanced then return 1 else return 0.



Problem Constraints



1 <= |A| <= 105



Input Format

First argument is an string A.

Output Format

Return 1 if parantheses in string are balanced else return 0.

Solution :

int Solution::solve(string A) {

    int l = A.length();

    stack<char>s;

    int f = 0;

    for(int i =0;i<l;i++){

        char c  = A[i];

        if(c == '('){

            s.push(c);

        }else{

            if(s.empty()){

                f = 1;

                break;

            }

            s.pop();

            }

        

    }

    if(f == 1){

        return 0;

    }

    if(!s.empty()){

        return 0;

    }

    return 1;

}

Reverse String | interviewBit | Solution | C++

Problem : 

Given a string S, reverse the string using stack.
Example :
Input : "abc" 
Return "cba"

Solution1 : 

string Solution::reverseString(string A) {

    reverse(A.begin(),A.end());

    return A;

    

}

Solution2 :

string Solution::reverseString(string A) {

    stack<char>s;

    int l = A.length();

    for(int i =0;i<l;i++){

        s.push(A[i]);

    }

    

    string rev = "";

    

    while(!s.empty()){

        rev+=s.top();

        s.pop();

    }

    

    return rev;

   

    

}

Queue Using Stack | Code | C++

#include<iostream>

#include<stack>

using namespace std;

stack<int>s1;

stack<int>s2;

void push(int element){

s1.push(element);

}

int pop(){

    if(!s2.empty()){

        int r = s2.top();

        s2.pop();

        return r;

    }else{

        while(!s1.empty()){

            int t = s1.top();

            s1.pop();

            s2.push(t);

        }

        int r = s2.top();

        s2.pop();

        return r;

    }

}

int main(){

// s1 and s2

 //push : 1 2 3 4

 //pop :  ->  1

 //push : 5    -> 2 3 4 5

 //pop :   -> 2

 push(1);

 push(2);

 push(3);

 push(4);

 cout<<pop();

 push(5);

 cout<<'\n'<<pop();

return 0;}

NOTE : Write code for queue properties and even do check for empty before popping the element from the queue ...

Stack Using STL : CODE | C++

// stack using STL

#include<stack>

#include<iostream>

using namespace std;

int main(){

stack<int>s;

// push

s.push(2);

s.push(4);

s.push(5);

s.push(7);

// 2 4 5 7

//pop

s.pop();  // removed 7

//top

cout<<" top = "<<s.top();  // 5 

// is empty

if(s.empty())cout<<"\nyes";

else cout<<"\nNO";

// size

cout<<" \nsize = "<<s.size();  // 3

}

Stack Using Linked List : Code ( C++ )

 

CODE:

// header file

#include<stdio.h>

#include<stdlib.h>

// struct

struct node{

int data;

struct node* next;

};

// operations

//push

void push(struct node ** head , int element){

struct node* p  = (struct node * )malloc(sizeof(struct node));

p->data = element;

//**head -> *head(top of the stack) -> stack

p->next = *head;

*head = p;

}

// isEmpty

int isEmpty(struct node *top){

return top == NULL;

}

// pop

int pop(struct node ** top ){

    if(isEmpty(*top)){

        return -1;

    }else{

        //**head -> *head(top of the stack) -> stack [1 , 2 ,3 ,...]

        //*p = 1

        //*head  = *head->next

        //free(p)

        struct node* p;

        p  = *top;

        *top = (*top)->next;

        int r = p->data;

        free(p);

        return r;

    }

}

// top

int peek(struct node* top){

if(!isEmpty(top)){

    return top->data;

}else{

return -1;

}

}

// main

int main(){

//**q = &*p = &a

struct node* top = NULL;

push(&top,1);

push(&top,2);

push(&top,3);

// 3  2   1

printf("%d",peek(top));

return 0;}

Code of Stack in C Using Array

// stack using array

// library

#include<stdio.h>

#include<stdlib.h>

// make structure   maxsize , top , *items

struct stack{

int maxSize;

int top;

int *items;

};

// initialization

struct stack* newStack(int capacity){

    struct stack *p =  (struct stack *)malloc(sizeof(struct stack));

    p->maxSize  = capacity;

    p->top = -1;

    p->items = (int *)malloc(sizeof(int) * capacity);

    return p;

}

// operations for our stack

// top

int top(struct stack* p ){

    return p->items[p->top];

}

// isEmpty

int isEmpty(struct stack* p ){

    return p->top == -1;

}

// isFull

int isFull(struct stack *p){

    return p->top + 1 == p->maxSize;

}

// size

int size(struct stack * p){

    return p->top + 1;

}

// push

void push(struct stack* p , int element){    //        12 3  4 4 3

    if(isFull(p)){

        printf("Overflow!\n");

    }else{

        p->items[++p->top] = element;

    }

}

// pop

int pop(struct stack * p ){

    if(isEmpty(p)){

        printf("Underflow!");

    }else{

        return p->items[p->top--];

    }

}

int main(){

struct stack * s = newStack(5);

push(s,1);

push(s,5);

push(s,3);

push(s,6);

//   1    5     3   6

printf("%d\n",top(s));

printf("%d",size(s));

return 0;

}

CREATING STACK IN PYTHON

CREATING STACK USING PYTHON

OPERATIONS:

1- PUSH

2- POP

OTHER OPERATIONS:

1- IS EMPTY

2- SIZE

3- TOP

CODE : 

We can implement stack using :

1- list

2- collections.deque

3- queue.LifoQueue

1 - IMPLEMENTING STACK USING LIST

CODE:

stack = []  // list is created to be used as stack
stack.append('a') // append() push the element in stack which is actually a list
stack.append('b')
stack.append('c')

print(stack.pop()) // pop() is used to pop / delete element on top of list

print(stack.pop())

print(stack.pop())

print(stack)

2- IMPLEMENTING STACK USING collections.deque

from collections import deque  // importing the library

stack = deque() // initializing a variable

stack.append('a') // append function to insert element

stack.append('b')

stack.append('c')

print(stack.pop())  // pop() function to remove the top element

print(stack.pop())

print(stack.pop())

print(stack)

3- IMPLEMENTING STACK USING queue module

Functions available in this module are :

1- get() - remove and return the element from queue

2- put(element) - put element in the queue

3- maxsize() - maximum elements allowed

4- empty() - check whether stack is empty or not

5- full() - check whether stack is full or not if maxsize is declared

6- qsize() - get number of items in queue

CODE:

from queue import LifoQueue
stack = LifoQueue(maxsize = 5) // initializing stack with maxsize = 5
print(stack.qsize()) // show the number of elements in the stack
stack.put('a')  // put() is used to push elements in the stack
stack.put('b')
stack.put('c')
print("Full: ", stack.full())  // is the stack full or does stack contain maxsize elements
print(stack.get()) // return and remove the top element of the stack
print(stack.get())
print(stack.get())
print("Is Empty : ", stack.empty()) // test is the stack empty or not

CREATING STACK USING STL

 STACK IN STL

Standard library provides us stack container with number of built in features.

STACK TEMPLATE :

template <class T, class Container = deque<T> > class stack;

MEMBER FUNCTIONS :

All these operations can be performed in 0(1)

empty  :  test whether the container is empty

size    : return the size of the container

top   : return the top element

push  : insert element

emplace  : construct and insert element

pop  : remove top element

swap  : swap contents

CODE ;

#include <iostream>
#include <stack>    // for using stack container
using namespace std;

int main()
{
int sum = 0;
stack<int> mystack; // declaring stack
mystack.push(21);   // inserting element
mystack.push(32);
mystack.push(23);
mystack.push(63);
mystack.push(212);

while (!mystack.empty()) {   // checking the empty condition
sum = sum + mystack.top();   // checking the top element
mystack.pop();               // performing pop operation
} 
cout << sum;
return 0;
}

 

IMPLEMENTING STACK USING LINKEDLIST

 IMPLEMENTING STACK USING LINKEDLIST

This provide us ability to define our own data structure and point it to another same data structure using pointers which can be done dynamically .

Here , Since we are using Linked list we will use malloc and free ( in C ) to allocate memory and then deallocate it when needed.

Structure or Linked list Node

Header Files

OPERATIONS

NOTE : Since  , performing operations on head is easy and efficient so  we will choose head node as top node and will perform all operations on head node 

1- PUSH

2- IS EMPTY

    

3- TOP

4- POP

IMPLEMENT STACK USING ARRAY

IMPLEMENTATION  USING ARRAY

DATA STRUCTURE

We will use structure to create stack that will have three things

1- Max Size : contains the maximum size stack can have or its capacity

2- Top : contains the index of the top element

3- items array or pointer to array : contains the elements of stack

Header Files :

operations to perform :

1- Initialization of stack

2- Getting size of stack

3- Check the status i.e. is the stack empty or not

4- Check the status i.e. is the stack full or not

5- Adding element to stack using Push operation

6- Removing the top of the stack using Pop operation

7- Getting the top of the stack

STACK : INTRODUCTION | OPERATIONS | REAL LIFE EXAMPLE | IMPLEMENTATION

 What Is Stack

. Linear Data Structure

TWO OPERATION : 

1 - PUSH : Entering the data on the top or at the end

2- POP : Remove the top element or latest element

So, Stack performs LIFO operation where LIFO stands for Last In First Out.

Nowadays every language has some more operations i.e. Peek, Is empty, Is full , size 

3 - PEEK : It help us to check the top entry without deleting it

4- IS EMPTY : this checks whether the stack is empty or not and provides boolean value (true / false)

5- IS FULL : this checks whether the stack is full or not in non dynamic data structure. If you are using standard library then it resize dynamically .

6- SIZE : this gives the size of the stack

Whenever you get stack , think it to be a data structure where you have to preform insertions and deletion on the same end what ever data structure you are using.

Real Life Example :

1- Plates stacked over one another

2- Stacked books

So , the book on top is the first book to be taken . Although it was the last book to place . Similarly

in marriages the top most dinner plate is the first plate to be taken and used.

APPLICATION OF STACK

1- Undo - Redo features 

2- Infix to Prefix or Postfix

3- Balancing the symbols

4- Used in Algorithms 

    a) Rat in maze

    b) N Queen Problem

    c) Tower of Hanoi

    d) Stock span problem

    e) Topological Sorting

    f) Strongly Connected Components

5- Syntax Parsing

6- Browser back button

7- Useful for performing operations like Backtracking in Programming

IMPLEMENTATION

You can use any data structure to perform this operation :

1- Array

2- Linkedlist

If you use standard library , you can use the data structure provided such as stack (we will see the implementation soon ) which is dynamic and provided certain operations.