离散数学 之 命题公式的主析取合取范式（java实现）

• 先求出变量个数
• 求出每种情况下的真值，形成的真值表用map存储
• 求值过程中用双栈结构
• 将map中数据转化成String
• 一下代码只允许变量是大写字母和 | & ! ( ) 五种符号

import java.util.*;

public class Test {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("输入吧！！！(res结束)");
            String s = scanner.nextLine();
            if (s == "res") {
                break;
            }
            process(s);
        }

    }

    //表达式
    static String string;
    //表达式中的变量
    static char[] chars;
    //每一种情况对应的真还是假
    static HashMap map = new HashMap<>();

    //主掉函数
    public static void process(String s) {
        if (s == null || s.length() == 0) {
            System.out.println("滚，二愣子，啥都不给我求个屁");
        }
        process_1(s);
        string = "";
        map.clear();
        chars = null;
    }

    private static void process_1(String s) {
        try {
            string = s;
            //取出表达式中的变量
            s = s.replaceAll("[^A-Z]", "");
            TreeSet set = new TreeSet();
            for (int i = 0; i < s.length(); i++) {
                set.add(s.charAt(i));//去重
            }
            chars = new char[set.size()];
            Iterator iterator = set.iterator();
            int index = 0;
            //遍历字符串用chars记录数据
            while (iterator.hasNext()) {
                chars[index++] = (Character) iterator.next();
            }
            //填充map，确定真值表
            process_1(0, "");

            //************** 将真值表的数据以主析取合取范式输出 ********************
            Iterator> entries = map.entrySet().iterator();
            String sT = "";
            String sF = "";
            while (entries.hasNext()) {
                Map.Entry next = entries.next();
                String v = next.getKey();
                if (next.getValue()) {
                    sT += "(";
                    for (int i = 0; i < chars.length; i++) {
                        if (v.charAt(i) == '1') {
                            sT += String.valueOf(chars[i]);
                        } else {
                            sT += "!" + chars[i];
                        }
                        if (i != chars.length - 1) {
                            sT += "&";
                        }
                    }
                    sT += ")|";
                } else {
                    sF += "(";
                    for (int i = 0; i < chars.length; i++) {
                        if (v.charAt(i) == '1') {
                            sF += String.valueOf(chars[i]);
                        } else {
                            sF += "!" + chars[i];
                        }
                        if (i != chars.length - 1) {
                            sF += "|";
                        }
                    }
                    sF += ")&";
                }
            }
            String s1=sT.substring(0, sT.length() - 1);
            String s2=sF.substring(0, sF.length() - 1);
            System.out.println("表达式：n" + string);
            System.out.println("主析取范式：n" + s1);
            System.out.println("主合取范式：n" + s2);
        } catch (Exception e) {
            System.out.println("表达式错误");
        }
    }


    //分为两种情况，0 或 1
    public static void process_1(int index, String thisTF) {

        if (chars.length == index) {
            //结束时计算该情况的真值情况，并记录在map中
            map.put(thisTF, getRes(thisTF));
            return;
        }
        process_1(index + 1, thisTF + "1");
        process_1(index + 1, thisTF + "0");
    }

    public static boolean getRes(String TorFList) {
        HashMap charMap = new HashMap<>();
        String str = new String(string);
        for (int i = 0; i < chars.length; i++) {
            str = str.replaceAll(String.valueOf(chars[i]), String.valueOf(TorFList.charAt(i)));
        }
        Stack stackOP = new Stack<>();
        Stack stackNum = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (isOper(c)) {
                if (c == '!' || stackOP.isEmpty() || c == '(') {
                    stackOP.push(c);
                    continue;
                }
                if (c == ')') {
                    while (stackOP.peek() != '(') {
                        char cha = stackOP.pop();
                        if (cha == '!') {
                            stackNum.push(reverse(stackNum.pop()));
                            continue;
                        }
                        stackNum.push(jisuan(stackNum.pop(), stackNum.pop(), cha));
                    }
                    stackOP.pop();
                    //特别注意 ( 前的 ! ,要在括号中元素运算时就要运算，否则会有问题
                    if (!stackOP.isEmpty() && stackOP.peek() == '!') {
                        stackOP.pop();
                        stackNum.push(reverse(stackNum.pop()));
                    }
                    continue;
                }
                stackOP.push(c);
            } else {
                stackNum.push(c);
            }
        }
        //将剩余元素做运算
        while (true) {
            if (stackOP.isEmpty()) {
                return stackNum.pop() == '1';
            }
            if (stackOP.peek() == '!') {
                stackOP.pop();
                stackNum.push(reverse(stackNum.pop()));
                continue;
            }
            Character a = stackNum.pop();
            Character b = stackNum.pop();
            Character c = stackOP.pop();
            stackNum.push(jisuan(a, b, c));
        }
    }

    private static boolean isOper(char ch) {
        return ch == '|' || ch == '&' || ch == '!' || ch == '(' || ch == ')';
    }

    private static char reverse(char ch) {
        return ch == '1' ? '0' : '1';
    }

    private static char jisuan(char a, char b, char ch) {
        if (ch == '|') {
            if (a == '0' && b == '0') {
                return '0';
            } else {
                return '1';
            }
        } else {
            if (a == '1' && b == '1') {
                return '1';
            } else {
                return '0';
            }
        }
    }
}