Check if two expressions with brackets are same | CPP program to check if two expressions evaluate to same . ; Return local sign of the operand . For example , in the expr a - b - ( c ) , local signs of the operands are + a , - b , + c ; Evaluate expressions into the count vector of the 26 alphabets . If add is true , then add count to the count vector of the alphabets , else remove count from the count vector . ; stack stores the global sign for operands . ; + means true global sign is positive initially ; global sign for the bracket is pushed to the stack ; global sign is popped out which was pushed in for the last bracket ; global sign is positive ( we use different values in two calls of functions so that we finally check if all vector elements are 0. ; global sign is negative here ; Returns true if expr1 and expr2 represent same expressions ; Create a vector for all operands and initialize the vector as 0. ; Put signs of all operands in expr1 ; Subtract signs of operands in expr2 ; If expressions are same , vector must be 0. ; Driver code
#include <bits/stdc++.h> NEW_LINE 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 expr1 , string expr2 ) { vector < int > v ( MAX_CHAR , 0 ) ; eval ( expr1 , v , true ) ; eval ( expr2 , v , false ) ; for ( int i = 0 ; i < MAX_CHAR ; i ++ ) if ( v [ i ] != 0 ) return false ; return true ; } int main ( ) { string expr1 = " - ( a + b + c ) " , expr2 = " - a - b - c " ; if ( areSame ( expr1 , expr2 ) ) cout << " Yes STRNEWLINE " ; else cout << " No STRNEWLINE " ; return 0 ; }