Dadas dos expresiones en forma de strings. La tarea es compararlos y comprobar si son similares. Las expresiones consisten en letras minúsculas, ‘+’, ‘-‘ y ‘( )’.
Ejemplos:
Input : exp1 = "-(a+b+c)"
exp2 = "-a-b-c"
Output : Yes
Input : exp1 = "-(c+b+a)"
exp2 = "-c-b-a"
Output : Yes
Input : exp1 = "a-b-(c-d)"
exp2 = "a-b-c-d"
Output : No
Se puede suponer que hay como máximo 26 operandos de ‘a’ a ‘z’ y cada operando aparece solo una vez.
Una idea simple detrás es llevar un registro del Signo Global y Local (+/-) a través de la expresión. El signo global aquí significa el signo multiplicativo en cada operando. El signo resultante de un operando es el signo local multiplicado por el signo global de ese operando.
Por ejemplo, la expresión a+b-(cd) se evalúa como (+)+a(+)+b(-)+c(-)-d => a + b – c + d. El signo global (representado entre paréntesis) se multiplica por el signo local de cada operando.
En la solución dada, la pila se usa para mantener un registro de los signos globales. Un vector de conteo registra los conteos de los operandos (letras latinas en minúscula aquí). Se evalúan dos expresiones de manera opuesta y, finalmente, se verifica si todas las entradas en el vector de conteo son ceros.
Implementación:
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] != '\0') {
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\n";
else
cout << "No\n";
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>
Producción
Yes
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Amol Mejari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA