Question

怎样用C++实现逻辑表达式转换成真值表的程序

就是像数子电路中的逻辑表达式一样，与或非的关系。做个程序能够实现输入一个逻辑表达式，结果输入该表达式的真值表。我主要想知道做这个程序的核心思想，就是要用到什么结构，怎样解决存储表达式的优先级关系。谢谢了

Answer 1

(P∧(P->Q))->Q
p->Q等价于(┐P)∨Q写成C/C++语言就是(!P)||Q
P∧(P->Q)等价于P∧((┐p)∨Q)写成C/C++就是P&&((!P)||Q))
(P∧(P->Q))->Q等价于(┐(P∧((┐p)∨Q)))∨Q写成C/C++语言就是(!(P&&((!P)||Q))))||Q
Programe Code:
#include <iostream>
using namespace std;
int main()
{
int Q,P;
cout<<"P Q (P∧(P->Q))->Q\n";
for(P=0;P<=1;P++)
for(Q=0;Q<=1;Q++)
cout<<P<<" "<<Q<<" "
<<((!(P&&((!P)||Q)))||Q)<<endl;
}
//运行结果
P Q (P∧(P->Q))->Q
0 0 1
0 1 1
1 0 1
1 1 1

其实你可以将表达式化简:
┐(P∧((┐p)∨Q))∨Q
<=> ┐((P∧┐p)∨(P∧Q)))∨Q
<=> ┐(0∨(P∨Q)))∨Q
<=> 1 ∨((┐(P∨Q))∨Q)
<=> 1

Answer 2

比较简单的一种是枚举输入量的组合值，所以计算复杂度是2^n，n表示变量个数。当然由于逻辑表达式比较简单，只有+ * 非 最后还有括号，比四则运算要简单的多。一个建议是使用修改的链表或者栈实现，毕竟输出真值表要枚举每个变量的真值。
建议的方式如下：使用链表或者数组存储表达式，节点类型可以自定义：包含一个指向外部的引用或者连接表示这个变量当前的值。然后使用栈将中缀表达式转化为后缀表达式进行压栈计算。依照枚举组合一次遍历链表。
请参考：数据结构-栈-四则计算（中缀表达式、后缀表达式）、链表、 以及《组合数学》组合生成算法