Check If Two Expressions With Brackets Are Same

Easy
0/40
Average time to solve is 16m
profile
Contributed by
7 upvotes
Asked in companies
Codalien Technologies42gearMobilitySystems

Problem statement

You are given two strings which are expressions in variables. You need to compare and tell if they are similar or different. You need to return “YES” for the same expressions and “NO” for different expressions. The expressions consist of lowercase alphabets, ‘+’, ‘-’ and ‘(‘, ‘)’. It may be assumed that there are at most 26 operands from ‘a’ to ‘z’.

Two expressions will be said as similar if they have the same set of operands and when some values are given to these operands, then both the expressions give the same result.

For example: 
If the first expression is: (a + (b + c)) and the second expression is: a + b + c. The expressions are the same because if they are evaluated, they will give the same output. So the answer is “YES”.
Note: 
You can assume that any expression is evaluated according to the BODMAS rule.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer T, representing the number of test cases. 

Then the T test cases follow.

The first line of each test case contains a string S1 denoting the first expression.

The second line of each test case contains a string S2 denoting the second expression.
Output Format: 
For each test case, print “YES” if the expressions are the same and “NO” if the expressions are not the same, on a separate line.
Note: 
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints: 
1 ≤ T ≤ 10
1 ≤ |S1|, |S2| ≤ 1000

Time Limit : 1 sec
Sample Input 1:
3
(a+(b+c))
a+b+c
a-(b-c)
a-b+c
(a-b)
-(-a-b)
Sample Output 1:
YES
YES
NO
Explanation For Sample Input 1:
The first test case has already been explained in the problem statement.

In the second test case,  the first expression is: a-(b-c) and the second expression is: a-b+c. The expressions are the same because if they are evaluated, they will give the same output i.e. a-b+c. So the answer is “YES”.

In the third test case, the first expression is: (a-b) and the second expression is: -(a-b). The expressions are different because if they are evaluated, the first expression will become: a-b and the second expression will become a+b.
Sample Input 2:
3
a+b+c
b+c+a
a-b-(c+d)
a-b-c-d
a-b-(c-d)
a-b-c-c
Sample Output 2
YES
YES
NO
Hint

How does the sign change from + to - and - to + ?

Approaches (1)
Optimal Solution
  • We keep track of the current sign, whether it is + or -
  • For example, the expression: a-(-b+c) evaluates to a+b-c. Here the sign of b and c are changed in the final expression.
  • We maintain a boolean stack for doing so. If it is true, that means character is added and if it is false, that means the character is removed.
  • We maintain a count array of size 26(since there are 26 lowercase alphabets). We keep a count of the number of characters of the first expression and the second expression.
  • When traversing the first expression, we increase the count when the character is added and decrease the count when it is removed.
  • In a similar way, when traversing the second expression, we decrease the count when the character is added and increase the count when it is removed.
  • Finally, we check if the count array has all elements 0 or not. If it does, we return “YES”, otherwise “NO”.
Time Complexity

O(N + M) where N and M are the sizes of the first and second expressions respectively.

 

This is because we would be traversing both expressions once.

Space Complexity

O(max(N, M)) where N and M are the sizes of the first and second expressions respectively. 

 

This is because we are maintaining a stack of size N for the first expression and a stack of size M for the second expression.

Code Solution
(100% EXP penalty)
Check If Two Expressions With Brackets Are Same
Full screen
Console