给定两个字符串形式的表达式。任务是比较它们并检查它们是否相似。表达式由小写字母“+”、“-”和“（）”组成。 例如：
null
Input : exp1 = "-(a+b+c)" exp2 = "-a-b-c"Output : YesInput : exp1 = "-(c+b+a)" exp2 = "-c-b-a"Output : YesInput : exp1 = "a-b-(c-d)" exp2 = "a-b-c-d"Output : No
可以假设从“a”到“z”最多有26个操作数，每个操作数只出现一次。
一个简单的想法是记录 全局和局部符号（+/-） 通过表达。这里的全局符号表示每个操作数的乘法符号。操作数的结果符号是本地符号乘以该操作数的全局符号。 例如，表达式a+b-（c-d）的计算结果为（+）+a（+）+b（-）+c（-）-d=>a+b–c+d。全局符号（用括号表示）乘以每个操作数的局部符号。 在给定的解决方案中，堆栈用于记录全局符号。计数向量记录操作数的计数（此处为小写拉丁字母）。以相反的方式计算两个表达式，最后检查计数向量中的所有条目是否为零。
C++
// CPP program to check if two expressions // evaluate to same. #include <bits/stdc++.h> using namespace std; const int MAX_CHAR = 26; // Return local sign of the operand. For example, // in the expr a-b-(c), local signs of the operands // are +a, -b, +c bool adjSign(string s, int i) { if (i == 0) return true ; if (s[i - 1] == '-' ) return false ; return true ; }; // 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. void eval(string s, vector< int >& v, bool add) { // stack stores the global sign // for operands. stack< bool > stk; stk.push( true ); // + means true // global sign is positive initially int i = 0; while (s[i] != ' ' ) { if (s[i] == '+' || s[i] == '-' ) { i++; continue ; } if (s[i] == '(' ) { // global sign for the bracket is // pushed to the stack if (adjSign(s, i)) stk.push(stk.top()); else stk.push(!stk.top()); } // global sign is popped out which // was pushed in for the last bracket else if (s[i] == ')' ) stk.pop(); else { // global sign is positive (we use different // values in two calls of functions so that // we finally check if all vector elements // are 0. if (stk.top()) v[s[i] - 'a' ] += (adjSign(s, i) ? add ? 1 : -1 : add ? -1 : 1); // global sign is negative here else v[s[i] - 'a' ] += (adjSign(s, i) ? add ? -1 : 1 : add ? 1 : -1); } i++; } }; // Returns true if expr1 and expr2 represent // same expressions bool areSame(string expr1, string expr2) { // Create a vector for all operands and // initialize the vector as 0. vector< int > v(MAX_CHAR, 0); // Put signs of all operands in expr1 eval(expr1, v, true ); // Subtract signs of operands in expr2 eval(expr2, v, false ); // If expressions are same, vector must // be 0. for ( int i = 0; i < MAX_CHAR; i++) if (v[i] != 0) return false ; return true ; } // Driver code int main() { string expr1 = "-(a+b+c)" , expr2 = "-a-b-c" ; if (areSame(expr1, expr2)) cout << "Yes" ; else cout << "No" ; return 0; } |
JAVA
// Java program to check if two expressions // evaluate to same. import java.io.*; import java.util.*; class GFG { static final int MAX_CHAR = 26 ; // Return local sign of the operand. For example, // in the expr a-b-(c), local signs of the operands // are +a, -b, +c static boolean adjSign(String s, int i) { if (i == 0 ) return true ; if (s.charAt(i - 1 ) == '-' ) return false ; return true ; }; // 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. static void eval(String s, int [] v, boolean add) { // stack stores the global sign // for operands. Stack<Boolean> stk = new Stack<>(); stk.push( true ); // + means true // global sign is positive initially int i = 0 ; while (i < s.length()) { if (s.charAt(i) == '+' || s.charAt(i) == '-' ) { i++; continue ; } if (s.charAt(i) == '(' ) { // global sign for the bracket is // pushed to the stack if (adjSign(s, i)) stk.push(stk.peek()); else stk.push(!stk.peek()); } // global sign is popped out which // was pushed in for the last bracket else if (s.charAt(i) == ')' ) stk.pop(); else { // global sign is positive (we use different // values in two calls of functions so that // we finally check if all vector elements // are 0. if (stk.peek()) v[s.charAt(i) - 'a' ] += (adjSign(s, i) ? add ? 1 : - 1 : add ? - 1 : 1 ); // global sign is negative here else v[s.charAt(i) - 'a' ] += (adjSign(s, i) ? add ? - 1 : 1 : add ? 1 : - 1 ); } i++; } }; // Returns true if expr1 and expr2 represent // same expressions static boolean areSame(String expr1, String expr2) { // Create a vector for all operands and // initialize the vector as 0. int [] v = new int [MAX_CHAR]; // Put signs of all operands in expr1 eval(expr1, v, true ); // Subtract signs of operands in expr2 eval(expr2, v, false ); // If expressions are same, vector must // be 0. for ( int i = 0 ; i < MAX_CHAR; i++) if (v[i] != 0 ) return false ; return true ; } // Driver Code public static void main(String[] args) { String expr1 = "-(a+b+c)" , expr2 = "-a-b-c" ; if (areSame(expr1, expr2)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by // sanjeev2552 |
Python3
# Python3 program to check if two expressions # evaluate to same. MAX_CHAR = 26 ; # Return local sign of the operand. For example, # in the expr a-b-(c), local signs of the operands # are +a, -b, +c def adjSign(s, i): if (i = = 0 ): return True ; if (s[i - 1 ] = = '-' ): return False ; return True ; # 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. def eval (s, v, add): # stack stores the global sign # for operands. stk = [] stk.append( True ); # + means True # global sign is positive initially i = 0 ; while (i < len (s)): if (s[i] = = '+' or s[i] = = '-' ): i + = 1 continue ; if (s[i] = = '(' ): # global sign for the bracket is # pushed to the stack if (adjSign(s, i)): stk.append(stk[ - 1 ]); else : stk.append( not stk[ - 1 ]); # global sign is popped out which # was pushed in for the last bracket elif (s[i] = = ')' ): stk.pop(); else : # global sign is positive (we use different # values in two calls of functions so that # we finally check if all vector elements # are 0. if (stk[ - 1 ]): v[ ord (s[i]) - ord ( 'a' )] + = ( 1 if add else - 1 ) if adjSign(s, i) else ( - 1 if add else 1 ) # global sign is negative here else : v[ ord (s[i]) - ord ( 'a' )] + = ( - 1 if add else 1 ) if adjSign(s, i) else ( 1 if add else - 1 ) i + = 1 # Returns True if expr1 and expr2 represent # same expressions def areSame(expr1, expr2): # Create a vector for all operands and # initialize the vector as 0. v = [ 0 for i in range (MAX_CHAR)]; # Put signs of all operands in expr1 eval (expr1, v, True ); # Subtract signs of operands in expr2 eval (expr2, v, False ); # If expressions are same, vector must # be 0. for i in range (MAX_CHAR): if (v[i] ! = 0 ): return False ; return True ; # Driver Code if __name__ = = '__main__' : expr1 = "-(a+b+c)" expr2 = "-a-b-c" ; if (areSame(expr1, expr2)): print ( "Yes" ); else : print ( "No" ); # This code is contributed by rutvik_56. |
C#
// C# program to check if two expressions // evaluate to same. using System; using System.Collections.Generic; public class GFG { static readonly int MAX_CHAR = 26; // Return local sign of the operand. For example, // in the expr a-b-(c), local signs of the operands // are +a, -b, +c static bool adjSign(String s, int i) { if (i == 0) return true ; if (s[i-1] == '-' ) return false ; return true ; } // 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. static void eval(String s, int [] v, bool add) { // stack stores the global sign // for operands. Stack<Boolean> stk = new Stack<Boolean>(); stk.Push( true ); // + means true // global sign is positive initially int i = 0; while (i < s.Length) { if (s[i] == '+' || s[i] == '-' ) { i++; continue ; } if (s[i] == '(' ) { // global sign for the bracket is // pushed to the stack if (adjSign(s, i)) stk.Push(stk.Peek()); else stk.Push(!stk.Peek()); } // global sign is popped out which // was pushed in for the last bracket else if (s[i] == ')' ) stk.Pop(); else { // global sign is positive (we use different // values in two calls of functions so that // we finally check if all vector elements // are 0. if (stk.Peek()) v[s[i] - 'a' ] += (adjSign(s, i) ? add ? 1 : -1 : add ? -1 : 1); // global sign is negative here else v[s[i] - 'a' ] += (adjSign(s, i) ? add ? -1 : 1 : add ? 1 : -1); } i++; } } // Returns true if expr1 and expr2 represent // same expressions static bool areSame(String expr1, String expr2) { // Create a vector for all operands and // initialize the vector as 0. int [] v = new int [MAX_CHAR]; // Put signs of all operands in expr1 eval(expr1, v, true ); // Subtract signs of operands in expr2 eval(expr2, v, false ); // If expressions are same, vector must // be 0. for ( int i = 0; i < MAX_CHAR; i++) if (v[i] != 0) return false ; return true ; } // Driver Code public static void Main(String[] args) { String expr1 = "-(a+b+c)" , expr2 = "-a-b-c" ; if (areSame(expr1, expr2)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to check if two expressions // evaluate to same. let MAX_CHAR = 26; // Return local sign of the operand. For example, // in the expr a-b-(c), local signs of the operands // are +a, -b, +c function adjSign(s, i) { if (i == 0) return true ; if (s[i - 1] == '-' ) return false ; return true ; } // 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. function eval(s, v, add) { // stack stores the global sign // for operands. let stk = []; stk.push( true ); // + means true // global sign is positive initially let i = 0; while (i < s.length) { if (s[i] == '+' || s[i] == '-' ) { i++; continue ; } if (s[i] == '(' ) { // global sign for the bracket is // pushed to the stack if (adjSign(s, i)) stk.push(stk[stk.length - 1]); else stk.push(!stk[stk.length - 1]); } // global sign is popped out which // was pushed in for the last bracket else if (s[i] == ')' ) stk.pop(); else { // global sign is positive (we use different // values in two calls of functions so that // we finally check if all vector elements // are 0. if (stk[stk.length - 1]) v[s[i] - 'a' ] += (adjSign(s, i) ? add ? 1 : -1 : add ? -1 : 1); // global sign is negative here else v[s[i] - 'a' ] += (adjSign(s, i) ? add ? -1 : 1 : add ? 1 : -1); } i++; } }; // Returns true if expr1 and expr2 represent // same expressions function areSame(expr1, expr2) { // Create a vector for all operands and // initialize the vector as 0. let v = new Array(MAX_CHAR); v.fill(0); // Put signs of all operands in expr1 eval(expr1, v, true ); // Subtract signs of operands in expr2 eval(expr2, v, false ); // If expressions are same, vector must // be 0. for (let i = 0; i < MAX_CHAR; i++) if (v[i] != 0) return false ; return true ; } let expr1 = "-(a+b+c)" , expr2 = "-a-b-c" ; if (areSame(expr1, expr2)) document.write( "YES" ); else document.write( "NO" ); // This code is contributed by suresh07. </script> |
输出：
YES
本文由 阿莫尔·梅贾里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
