合（析）取范式转主合（析）取范式--》Java实现

原文地址：合（析）取范式转主合（析）取范式--》Java实现

介绍

这次老师布置了如下上机作业，不限语言。思前想后，问了几个大神，说了一堆不知道什么鬼的算法名称。。。。

经过一番百度，发现Java可以包含库然后使用JavaScript的一些函数，其中 eval() 函数可计算某个字符串，并执行其中的的 JavaScript 代码。http://www.w3school.com.cn/jsref/jsref_eval.asp 想到了如下解决办法。。

代码实现

import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;
import java.util.*;


/**
* Creat by Qjm
*/
public class Test {

    //A-Z 65-90
    //a-z 97-122
    public static Map<Integer, Integer> m = new HashMap<Integer, Integer>();
    public static int count = 0;
    public static List<String> list_true_value = new ArrayList<String>();

    /**
     * 获取主和取（析取）范式
     * String @param problem    要转换的命题公式
     * int @param flag          标记（1 ：和取    2：析取）
     *
     * @return
     * @throws ScriptException
     */
    public static String getMainNormalForm(String problem, int flag) throws ScriptException {
        ScriptEngineManager manager = new ScriptEngineManager();
        ScriptEngine engine = manager.getEngineByName("js");
        problem = problem.trim().toUpperCase();
        char[] pro_arr = problem.toCharArray();
        Set<String> s_variable = new LinkedHashSet<String>();
        for (char temp : pro_arr) {
            if (temp >= 65 && temp <= 90) {
                s_variable.add(temp + "");
                //System.out.println(temp+"");
            }
        }


        String[] variables = (String[]) s_variable.toArray(new String[0]);
        Arrays.sort(variables);
        System.out.println("\n真值指派顺序：" + Arrays.toString(variables));
        method(engine, variables, variables.length, problem);
        String result1 = "Σ(";
        String result2 = "∏(";
        String temp1 = "";
        String temp2 = "";
        for (Integer i : m.keySet()) {
            if (m.get(i) == 1) {
                result1 += i + ",";
                temp1 += "m" + i + "∨";
            } else {
                result2 += i + ",";
                temp2 += "M" + i + "∧";
            }
        }
        result1 = result1.substring(0, result1.length() - 1);
        result2 = result2.substring(0, result2.length() - 1);
        temp1 = temp1.substring(0, temp1.length() - 1);
        temp2 = temp2.substring(0, temp2.length() - 1);
        result1 += ")";
        result2 += ")";

        count = 0;
        m.clear();

        return flag == 1 ? temp2 + "\n" + result2 : temp1 + "\n" + result1;
    }


    /**
     * 递归函数，给每一个命题变远指派真值，得出每一种真值指派的结果
     * ScriptEngine @param engine
     * String[] @param variables
     * int @param times   命题变元的个数
     * String @param problem   要转换的命题公式
     * 将注释掉的打印输出取消，可以看到该算法的具体执行过程
     * @throws ScriptException
     */
    public static void method(ScriptEngine engine, String[] variables, int times, String problem) throws ScriptException {
        if (times < 1) {
            Integer result = (Integer) engine.eval(problem);
            
            //System.out.println("" + problem + "");
            //System.out.println("结果类型:" + result.getClass().getName() + ",计算结果:" + result + "");
            m.put(count, result);
            count++;
            //System.out.println(transMapToString(m));
            return;
        } else {
            for (int i = 0; i < 2; i++) {
                engine.put(variables[variables.length - times], i);
                //System.out.println("\ntimes : " + times + "\nbool :" + variables[times - 1] + "--->" + i);
                method(engine, variables, times - 1, problem);
            }
        }

    }

    /**
    /**
     * 方法名称:transMapToString
     * 传入参数:map
     * 返回值:String 形如 username'chenziwen^password'1234
     */
    public static String transMapToString(Map map) {
        Set s = map.keySet();
        String temp = "";
        for (Object i : s) {
            temp += "key : " + (Integer) i + "\t\tvalue : " + map.get(i) + "\n";
        }
        return temp;
    }


    public static void main(String[] args) throws ScriptException {
        String problem = "";
        int flag = 0;
        Scanner s = new Scanner(System.in);
        while (true) {
            System.out.println("请输入要转换的合（析）取范式(&->合取  |->析取  !->非)：");
            try{
                problem = s.next();
            }catch(NoSuchElementException exception){
                System.out.println("mdzz");
                System.exit(0);
            }
            System.out.println("待转化的命题公式：" + problem);
            System.out.println("以下是对应的真值表");
            System.out.println("主合取范式： " + getMainNormalForm(problem, 1));
            System.out.println("主析取范式： " + getMainNormalForm(problem, 2) + "\n");
        }

    }
}

基本思路是：

• 首先，engine.eval(problem); 可以直接把字符串当作数学表达式运行
• 然后，engine.put(variables[variables.length - times], i); 可以直接把字符串中的指定字符换为目标数据，，这样就可以实现对表达式的每一个命题变元的真值指派。
• 再利用递归函数实现类似真值表法的遍历， 再记录每一次真值指派的表达式的真值，再化为对应的表达式。

运行效果