Color The Code: code

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;

}

Monday, November 23, 2020

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;

}

Sunday, November 22, 2020

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;


}

Wednesday, November 4, 2020

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

Tuesday, November 3, 2020

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

}

Friday, October 30, 2020

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;
}