Check if Two Expressions With Brackets are Same

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.

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

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.

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

References