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;

   

    

}