C++ 实现给定布尔表达式所需的最少基本逻辑门数目

逻辑门 是数字电路的基本构件。它们接受一个或两个二进制输入，并返回一个二进制输出。由于使用二进制术语，输出和输入可以是0或1，或者可以说为“假”和“真”或“低”和“高”。

共有3种基本逻辑门−

与门

与门有两个或更多个输入和一个输出。如果所有输入都是高电平，则它产生一个高电平输出。以下是一个两个输入与门的真值表−

或门

或门具有两个或更多的输入和一个输出。如果任何一个输入为高电平，则产生一个高电平输出。以下是一个两输入或门的真值表－

非门

非门有一个输入和一个输出。当输入低时，它产生高输出；当输入高时，它产生低输出。非门的真值表如下所示−

这三个基本逻辑门可以组合成更复杂的电路，例如NAND门，NOR门和XOR门。

布尔表达式 − 它是一个包含一个或多个变量、逻辑运算符和常数的数学表达式。变量的值可以是0或1，并且用a、b、c等表示。布尔表达式中常用的逻辑运算符通常有AND、OR和NOT。这些运算符以一种能够定义变量或常数之间的关系的方式来组合变量和常数。

例如，布尔表达式A AND B只有在变量A和B都为真时才为真。布尔表达式A OR B只有在变量A或变量B中至少有一个为真时才为真。布尔表达式NOT A只有在变量A为假时才为真。

布尔表达式经常在编程、电路设计和数字电子技术中用于表示逻辑操作、条件和变量之间的逻辑关系。

问题陈述

给定一个定义布尔表达式的字符串str。找出实现给定表达式所需的最小逻辑门数量。

输入 –

str = “!A.B+C”

输出 –

3

解释

这个表达式使用1个用‘!’表示的NOT门，1个用‘.’表示的AND门，和1个用‘+’表示的OR门。总共有3个基本逻辑门。

示例2

输入 −

str = “!(a+b)+c.d”

输出 –

4

解释

该表达式使用了1个取反门（用‘!’表示）、2个与门（用‘.’表示）和1个或门（用‘+’表示）。因此，总共有4个基本逻辑门。

解决方案方法

为了实现布尔表达式的总逻辑门数，我们需要计算字符串中出现的逻辑门总数，并根据它们的符号表示来识别它们。

• 与门用‘.’表示

• 或门用‘+’表示

• 取反门用‘!’表示

伪代码

procedure numberOfGates (s)
n = length(s)
   count = 0
   for i = 1 to n
      if s[i] equals '.' or s[i] equals '+' or s[i] equals '!'
         count = count + 1
      end if
   end for
   output count
end procedure

示例：C++实现

在下面的程序中，我们遍历布尔表达式并根据它们的出现次数计算门的数量。

#include <bits/stdc++.h>
using namespace std;
// Function to find the number of basic logic gates used in a boolean expression
void numberOfGates(string s){

   // Calculating the size of the string
   int n = s.size();

   // Initialising count variable
   int count = 0;

   // Traversing the string to find the gate's symbols
   for (int i = 0; i < n; i++) {

      // Incrementing counter on the occurrence of AND, OR or NOT gate
      if (s[i] == '.' || s[i] == '+' || s[i] == '!') {
         count++;
      }
   }
   cout << count;
}
int main(){
   string str = "!a+b";
   cout << "Boolean Exoression: " << str << endl;
   cout << "Minimum number of basic logic gate required: " ;
   numberOfGates(str);
}

输出

Boolean Exoression: !a+b
Minimum number of basic logic gate required: 2

结论

总之，要找到实现给定布尔表达式所需的基本逻辑门的最小数量，我们可以有效地使用numberOfGates()函数。该函数以定义布尔表达式的字符串作为输入，并输出实现该表达式所需的最小门数。减少逻辑门的数量对于降低电路的成本和复杂性非常重要。

总体而言，该代码是计算实现布尔表达式所需的基本逻辑门数量的一种简单有效的方法，并且可以在更复杂的数字电路中轻松适应使用。