Dada una string S de longitud N que representa una expresión booleana , la tarea es encontrar el número mínimo de compuertas AND, OR y NOT necesarias para realizar la expresión dada.
Ejemplos:
Entrada: S = “A+BC”
Salida: 2
Explicación: Realizar la expresión requiere 1 compuerta AND representada por ‘.’ y 1 compuerta OR representada por ‘+’.Entrada: S = “(1 – A). B+C”
Salida: 3
Explicación: Realizar la expresión requiere 1 compuerta AND representada por ‘.’ y 1 puerta OR representada por ‘+’ y 1 puerta NOT representada por ‘-‘.
Enfoque: siga los pasos a continuación para resolver el problema:
- Iterar sobre los caracteres de la string .
- Inicializar, cuenta de puertas a 0 .
- Si el carácter actual es ‘.’ o ‘+’ , o ‘1’ , luego incremente el conteo de puertas en 1
- Imprime el conteo de puertas requeridas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of // the above approach #include <bits/stdc++.h> using namespace std; // Function to count the total // number of gates required to // realize the boolean expression S void numberOfGates(string s) { // Length of the string int N = s.size(); // Stores the count // of total gates int ans = 0; // Traverse the string for (int i = 0; i < (int)s.size(); i++) { // AND, OR and NOT Gate if (s[i] == '.' || s[i] == '+' || s[i] == '1') { ans++; } } // Print the count // of gates required cout << ans; } // Driver Code int main() { // Input string S = "(1-A).B+C"; // Function call to count the // total number of gates required numberOfGates(S); }
Java
// Java implementation of // the above approach class GFG{ // Function to count the total // number of gates required to // realize the boolean expression S static void numberOfGates(String s) { // Length of the string int N = s.length(); // Stores the count // of total gates int ans = 0; // Traverse the string for(int i = 0; i < (int)s.length(); i++) { // AND, OR and NOT Gate if (s.charAt(i) == '.' || s.charAt(i) == '+' || s.charAt(i) == '1') { ans++; } } // Print the count // of gates required System.out.println(ans); } // Driver Code public static void main(String[] args) { // Input String S = "(1-A).B+C"; // Function call to count the // total number of gates required numberOfGates(S); } } // This code is contributed by user_qa7r
Python3
# Python3 implementation of # the above approach # Function to count the total # number of gates required to # realize the boolean expression S def numberOfGates(s): # Length of the string N = len(s) # Stores the count # of total gates ans = 0 # Traverse the string for i in range(len(s)): # AND, OR and NOT Gate if (s[i] == '.' or s[i] == '+' or s[i] == '1'): ans += 1 # Print the count # of gates required print(ans, end = "") # Driver Code if __name__ == "__main__": # Input S = "(1-A).B+C" # Function call to count the # total number of gates required numberOfGates(S) # This code is contributed by AnkThon
C#
// C# implementation of // the above approach using System; public class GFG { // Function to count the total // number of gates required to // realize the boolean expression S static void numberOfGates(string s) { // Length of the string int N = s.Length; // Stores the count // of total gates int ans = 0; // Traverse the string for(int i = 0; i < s.Length; i++) { // AND, OR and NOT Gate if (s[i] == '.' || s[i] == '+' || s[i] == '1') { ans++; } } // Print the count // of gates required Console.WriteLine(ans); } // Driver Code public static void Main(string[] args) { // Input string S = "(1-A).B+C"; // Function call to count the // total number of gates required numberOfGates(S); } } // This code is contributed by AnkThon
Javascript
<script> // JavaScript program for the above approach // Function to count the total // number of gates required to // realize the boolean expression S function numberOfGates(s) { // Length of the string let N = s.length; // Stores the count // of total gates let ans = 0; // Traverse the string for(let i = 0; i < s.length; i++) { // AND, OR and NOT Gate if (s[i] == '.' || s[i] == '+' || s[i] == '1') { ans++; } } // Print the count // of gates required document.write(ans); } // Driver Code // Input let S = "(1-A).B+C"; // Function call to count the // total number of gates required numberOfGates(S); </script>
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por apratyush41 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA