Check if two expressions with brackets are same
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.

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

Question

Check if two expressions with brackets are same

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.

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

Accepted Answer

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

Space Complexity: OtherExplanation:

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.

Time Complexity: OtherExplanation:

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.

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:

Note:

Input Format:

Output Format:

Note:

Constraints:

Top 42Gears Mobility Systems Mts1 interview questions & answers

Popular interview questions of Mts1