话不多说直接上代码
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
import java.util.Stack;
public class Solution {
static char[] alpha;
static String result;
static HashMap map = new HashMap();//键值对
static ArrayList> trueList = new ArrayList>();//结果为真的列表，用于计算主析取范式
static ArrayList> falseList = new ArrayList>();//结果为假的列表，用于计算主合取范式
public static String preProcess(String str) {//预处理
boolean flag = true;
int cur = 0;
while (flag) {
flag = false;
for (int i = cur; i < str.length(); i++) {
if (str.charAt(i) == '<' || str.charAt(i) == '>') {//对于->和<=>两种符号，这里把<>都去掉，以-和=代替
String str1 = str.substring(0, i);
String str2 = str.substring(i + 1, str.length());
str = str1.concat(str2);
flag = true;
cur = i;
break;
}
if(str.charAt(i) == '!') {//对于连续的!, 先统计共有多少i
int count = 1;
while(str.charAt(i + count) == '!') {
count++;
}
if(count % 2 == 1) {//奇数个！,则取第一个！,跳过中间偶数个！
String str1 = str.substring(0, i + 1);
String str2 = str.substring(i + count, str.length());
str = str1.concat(str2);
flag = true;
cur = i + 1;//下一次遍历从新str的！后一个字符开始遍历
break;
}else {//偶数个！,则跳过所有！
String str1 = str.substring(0, i);
String str2 = str.substring(i + count, str.length());
str = str1.concat(str2);
flag = true;
cur = i;//下一次遍历从新的str的记录点开始遍历
break;
}
}
}
}
return str;
}
public static String RPN(String str) {//逆波兰
char[] chars = str.toCharArray();
int pre = 0;
boolean charactor; // 是否为字母（只要不是运算符，都是字母），用于截取字符串
int len = chars.length;
int bracket = 0; // 左括号的数量
String result = "";
Stack output = new Stack();
Stack operators = new Stack<>();
for (int i = 0; i < len;) {
pre = i;
charactor = Boolean.FALSE;
// 截取数字
while (i < len && !Operator.isOperator(chars[i])) {
i++;
charactor = Boolean.TRUE;
}
if (charactor) {
output.push(str.substring(pre, i));
} else {
char o = chars[i++]; // 运算符
if (o == '(') {
bracket++;
}
if (bracket > 0) {
if (o == ')') {
while (!operators.empty()) {
char top = operators.pop();
if (top == '(') {
break;
}
output.push(top);
}
bracket--;
} else {
// 如果栈顶为 ( ，则直接添加，不顾其优先级
// 如果之前有 ( ，但是 ( 不在栈顶，则需判断其优先级，如果优先级比栈顶的低，则依次出栈
while (!operators.empty() && operators.peek() != '('
&& Operator.cmp(o, operators.peek()) <= 0) {
output.push(operators.pop());
}
operators.push(o);
}
} else {
while (!operators.empty() && Operator.cmp(o, operators.peek()) <= 0) {
output.push(operators.pop());
}
operators.push(o);
}
}
}
// 遍历结束，将运算符栈全部压入output
while (!operators.empty()) {
output.push(operators.pop());
}
while (!output.isEmpty()) {
result = output.pop() + result;
}
return result;
}
public static String alphaTable(String str) {//得出公式字母表
char[] carray = str.toCharArray();
String alpha = "";
for(int i = 0; i < str.length(); i++) {
if((carray[i] >= 'A' && carray[i] <= 'Z') || (carray[i] >= 'a' && carray[i] <= 'z')) {
alpha = alpha + carray[i];
}
}
return alpha;
}
public static boolean calculate(String str) {//计算公式，得出结果值
Stack calStack = new Stack();
char[] carray = str.toCharArray();
boolean cur, pre, post, result;
for(int i = 0; i < str.length(); i++) {
if(carray[i] == '!') {
cur = calStack.pop();
result = !cur;
}else if(carray[i] == '&') {
post = calStack.pop();
pre = calStack.pop();
result = pre && post;
}else if(carray[i] == '|') {
post = calStack.pop();
pre = calStack.pop();
result = pre || post;
}else if(carray[i] == '-') {
post = calStack.pop();
pre = calStack.pop();
if(pre == true && post == false) {
result = false;
}else {
result = true;
}
}else if(carray[i] == '=') {
post = calStack.pop();
pre = calStack.pop();
if(pre == post) {
result = true;
}else {
result = false;
}
}else{
result = map.get(carray[i]);
}
calStack.push(result);
}
return calStack.peek();
}
public static void dfs(int cur) {//遍历，赋每个字母真假值 进真假表
if(cur == alpha.length) {
boolean ans = calculate(result);
ArrayList aL = new ArrayList();
for(int i = 0; i < alpha.length; i++) {
aL.add(map.get(alpha[i]));
System.out.printf("%ct", map.get(alpha[i]) == true ? 'T' : 'F');
}
if(ans) {
trueList.add(aL);
System.out.println('T');
}else {
falseList.add(aL);
System.out.println('F');
}
return;
}
map.put(alpha[cur], true);
dfs(cur + 1);
map.put(alpha[cur], false);
dfs(cur + 1);
}
public static void printTable() {//打印真值表
System.out.println("真值表为");
for(int i = 0; i < alpha.length; i++) {
System.out.printf("%ct", alpha[i]);
}
System.out.println("A");
for(int i = 0; i < alpha.length * 9; i++) {
System.out.print('-');
}
System.out.println();
dfs(0);
}
public static void printFormula() {//打印主析取范式和主合取范式
System.out.println("主析取范式为");
for(int i = 0; i < trueList.size(); i++) {
System.out.print("(");
for(int j = 0; j < trueList.get(i).size(); j++) {
if(trueList.get(i).get(j) == true) {
System.out.print(alpha[j]);
}else {
System.out.print("┐" + alpha[j]);
}
if(j != trueList.get(i).size() - 1) {
System.out.print("∧");
}
}
System.out.print(")");
if(i != trueList.size() - 1) {
System.out.print("∨");
}
}
System.out.println();
System.out.println("主合取范式为");
for(int i = 0; i < falseList.size(); i++) {
System.out.print("(");
for(int j = 0; j < falseList.get(i).size(); j++) {
if(falseList.get(i).get(j) == false) {
System.out.print(alpha[j]);
}else {
System.out.print("┐" + alpha[j]);
}
if(j != falseList.get(i).size() - 1) {
System.out.print("∨");
}
}
System.out.print(")");
if(i != falseList.size() - 1) {
System.out.print("∧");
}
}
}
public static void main(String[] args) {
String str = "";
System.out.println("请输入公式");
System.out.println("&: 与运算, |: 或运算, !: 非运算, ->: 单条件运算, <=>: 双条件运算, (): 左右括号");
Scanner scanner = new Scanner(System.in);
str = scanner.nextLine();//读取公式
scanner.close();
String pstr = preProcess(str);//预处理
result = RPN(pstr);//后缀表达式
alpha = alphaTable(result).toCharArray();//字母表
printTable();//打印真值表
printFormula();//打印主析取范式，主合取范式
}
}
enum Operator {//符号操作符枚举
AND('&', 1), OR('|', 1), SINGLE('-', 1), DOUBLE('=', 1), NOT('!', 2), LEFT_BRACKET('(', 3), RIGHT_BRACKET(')', 3); // 括号优先级最高
char value;
int priority;
Operator(char value, int priority) {
this.value = value;
this.priority = priority;
}
public static int cmp(char c1, char c2) {//比较优先级
int p1 = 0;
int p2 = 0;
for (Operator o : Operator.values()) {
if (o.value == c1) {
p1 = o.priority;
}
if (o.value == c2) {
p2 = o.priority;
}
}
return p1 - p2;
}
public static boolean isOperator(char c) {//是否为操作符
for (Operator o : Operator.values()) {
if (o.value == c) {
return true;
}
}
return false;
}
}
有问题可留言
