Home » Technical Interview Questions » Stack Interview Questions » Check if Two Expressions With Brackets are Same

Check if Two Expressions With Brackets are Same


Difficulty Level Medium
Frequently asked in Amazon Oracle Walmart Labs
Hike Snapdeal Stack String Wipro Yatra Zoho

Given two strings s1 and s2 representing expressions containing addition operator, subtraction operator, lowercase alphabets, and parenthesis. Check if two expressions with brackets are the same.

Check if Two Expressions With Brackets are Same

Example

Input 

s1 = “-(a+b+c)”

s2 = “-a-b-c”

Output 

Yes

Input 

s1 = “a-b-(c-d)”

s2 = “a-b-c-d”

Output

No

Algorithm to Check if Two Expressions With Brackets are Same

  1. Initialize two strings s1 and s2 representing_expressions containing addition operator, subtraction_operator, lowercase alphabets, and parenthesis.
  2. Create a vector and initialize all the values of the vector as 0.
  3. After that create a stack of boolean type and push true in it.
  4. Traverse through the string 1 i.e. s1 and check if the character at the current index in the string is equal to ‘+’ or ‘-‘, go to the next iteration.
  5. Else if the character at the current index in the string is equal to an opening parenthesis, check if the character at the previous index in the string is not equal to ‘-‘, push the value at top of the stack in the stack itself else push the not of the value at top of the stack in the stack itself.
  6. If 5 step did not check then Else if the character at the current index in the string is equal to a closing parenthesis, pop the element at the top the stack.
  7. Else check if the stack has top, update the vector as v[s1[i]-‘a’]  +=(adjSign(s1,i) ? add ? 1 : -1 : add ? -1 : 1) else update the vector as v[s1[i]-‘a’]  +=(adjSign(s1,i) ? add ? -1 : 1 : add ? 1 : -1).
  8. Similarly, repeat the same steps with string 2 i.e. s2.
  9. After that, traverse from 0 to 25 and check if the value at the current index in the vector if not equal to 0, print “No” else print “Yes”.
READ  Find Maximum Sum Possible Equal Sum of Three Stacks

C++ Program to Check if Two Expressions With Brackets are Same

#include <bits/stdc++.h> 
using namespace std; 
  
const int MAX_CHAR = 26; 
  
bool adjSign(string s, int i){ 
    if(i == 0){ 
        return true;
    }
    
    if(s[i - 1] == '-'){ 
        return false; 
    }
    
    return true; 
}; 
  
void eval(string s, vector<int>& v, bool add){ 
    stack<bool> stk; 
    stk.push(true); 
  
    int i = 0; 
    while(s[i] != '\0'){ 
        if(s[i] == '+' || s[i] == '-'){ 
            i++; 
            continue; 
        } 
        
        if(s[i] == '('){ 
            if(adjSign(s, i)){  
                stk.push(stk.top());
            }
            else{ 
                stk.push(!stk.top()); 
            }
        } 
  
        else if(s[i] == ')'){  
            stk.pop(); 
        }
          
        else{ 
            if(stk.top()){                  
                v[s[i] - 'a'] += (adjSign(s, i) ? add ? 1 : -1 : add ? -1 : 1); 
            }
  
            else{                 
                v[s[i] - 'a'] += (adjSign(s, i) ? add ? -1 : 1 : add ? 1 : -1); 
            }
        } 
        i++; 
    } 
}; 
  
bool areSame(string s1, string s2){ 
    vector<int> v(MAX_CHAR, 0); 
  
    eval(s1, v, true); 
  
    eval(s2, v, false); 
  
    for(int i = 0; i < MAX_CHAR; i++){ 
        if(v[i] != 0){  
            return false;
        }
    }
  
    return true; 
} 
  
int main(){ 
    string s1 = "-(a+b+c)", s2 = "-a-b-c"; 
    
    if(areSame(s1, s2)){ 
        cout << "Yes\n"; 
    }
    else{
        cout << "No\n"; 
    }
    
    return 0; 
}
Yes

Java Program to Check if Two Expressions With Brackets are Same

import java.io.*; 
import java.util.*; 
  
class CheckExpressions{ 
  
    static final int MAX_CHAR = 26; 
  
    static boolean adjSign(String s, int i){ 
        if(i == 0){ 
            return true;
        }
        
        if(s.charAt(i - 1) == '-'){ 
            return false; 
        }
        
        return true; 
    }; 
  
    static void eval(String s, int[] v, boolean add){ 
  
        Stack<Boolean> stk = new Stack<>(); 
        stk.push(true); 
  
        int i = 0; 
        while(i < s.length()){ 
            if(s.charAt(i) == '+' || s.charAt(i) == '-'){ 
                i++; 
                continue; 
            } 
            
            if(s.charAt(i) == '('){ 
                if(adjSign(s, i)){ 
                    stk.push(stk.peek());
                }
                
                else{
                    stk.push(!stk.peek()); 
                }
            } 
  
            else if(s.charAt(i) == ')'){ 
                stk.pop(); 
            }
  
            else{ 
                if(stk.peek()){ 
                    v[s.charAt(i) - 'a'] += (adjSign(s, i) ? add ? 1 : -1 : add ? -1 : 1); 
                }
  
                else{
                    v[s.charAt(i) - 'a'] += (adjSign(s, i) ? add ? -1 : 1 : add ? 1 : -1); 
                }
            } 
            i++; 
        } 
    }; 
  
    static boolean areSame(String s1, String s2){ 
  
        int[] v = new int[MAX_CHAR]; 
  
        eval(s1, v, true); 
  
        eval(s2, v, false); 
  
        for(int i = 0; i < MAX_CHAR; i++){ 
            if(v[i] != 0){ 
                return false; 
            }
        }
  
        return true; 
    } 
  
    public static void main(String[] args){ 
  
        String s1 = "-(a+b+c)", s2 = "-a-b-c"; 
        
        if(areSame(s1, s2)){ 
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
    } 
}
Yes

Complexity Analysis

Time Complexity: O(max(n1, n2)) where n1 and n2 are the length of the given strings s1 and s2 respectively.

READ  Tracking current Maximum Element in a Stack

Space Complexity: O(max(n1, n2)) because we used space to store the characters of the given strings.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup