我最近参加了 Java 开发人员职位的面试。我接到了一项任务:想出一种用 Java 表示电路(如下图中的电路)的好方法。

电路是逻辑门 XOR、AND、OR 等的组合。每个门都有两个输入端口和一个输出端口。每个输出都连接到另一个门的输入，一直到更高的门(如图所示)。使系统简单，不允许有循环(尽管现实生活中的电路可以有循环)。 我被要求考虑使用以下准则在 Java 中表示此模型的好方法:

1. 我得到了一个电路和一个应该提供给它的输入的值列表。
2. 我需要创建一个模型来用 Java 表示电路，即，我需要定义可用于表示电路的类和 API。
3. 根据输入值和门的连接方式，我需要计算所表示的电路将产生的输出。
4. 我需要考虑一种表示板的方法，使用抽象类或接口(interface)，并展示对模型的理解(如果需要，还可以使用模式设计)。

我选择将系统设计成一棵树，面试官告诉我这是一个不错的选择。然后我构建这些类:

节点

public class gate_node {
    gate_node right_c,left_c;
    Oprtator op;
    int value;
    int right_v,left_v;
    public gate_node(gate_node right,gate_node left,Oprtator op){
        this.left_c=left;
        this.right_c=right;
        this.op=op;
        right_v=left_v=0;
    }
    
}

树

public class tree {
    gate_node head;

    tree(gate_node head) {
        this.head = head;
    }

    void go_right() {
        head = head.right_c;
    }

    void go_left() {
        head = head.left_c;
    }

    static int arr[] = { 0, 0, 1, 0 };
    static int counter=0;

    static int compute(gate_node head) {

        if ((head.left_c == null) && (head.right_c == null))
        {
            int ret=(head.op.calc(arr[counter], arr[counter+1]));
            counter++;
            counter++;
            return ret;
        }
        return (head.op.calc(compute(head.left_c), compute(head.right_c)));

    }

    public static void main(String[] args) {
        tree t = new tree(new gate_node(null, null, new and()));
        t.head.left_c = new gate_node(null, null, new and());
        t.head.right_c = new gate_node(null, null, new or());
        System.out.println(tree.compute(t.head));
    }
}

运算符类:

public abstract class Oprtator {
        abstract int calc(int x, int y);
}

或门:

public class or extends Oprtator {
        public int calc(int x, int y){
            return (x|y);
        }
}

在上面的代码中，我将棋盘实现为一棵树，它有一个当前头部(可以向下延伸到左/右子节点)。每个节点都有 2 个子节点(也是节点类型)、2 个条目 (0/1)、一个值和一个运算符(抽象类，可以通过 OR/AND.. 扩展)。

我使用一个计数器和一个数组将值插入树的适当叶子(如代码中所述)。

它有效，但我仍然觉得我的面试官想要更多东西。我的代码正确吗？有没有人有更好的方式来表示这个电路板以及如何提供良好的输出(在复杂性或使用更好的从一个类到另一个类的连接、设计模式等方面？)

最佳答案

这不是一个“完美”的答案，但您可以使用几个类来保存逻辑连接/评估然后递归评估电路来解决这个问题。

创建一个基类 LogicalNode 并为其提供要管理的输入列表。给它一个基类函数来评估所有输入并返回一个输出。这在派生类中被覆盖。每种类型的节点(INPUT、NOT、AND、OR)都获得一个派生类，该派生类具有特殊的“ComputOutput”覆盖版本。如果您计算输出节点的输出，它应该向上递归树，计算输入的所有输入等，直到它到达“INPUT”节点，这些节点是系统的固定/逻辑输入。

您可以相当快速地创建新类型(参见代码)。这里的评论不多，但应该是不言自明的。

像这样(在 C# 中):

public class LogicalNode
    {
        private List<LogicalNode> _inputs = new List<LogicalNode>();
        private String _name = "Not Set";


        public override string ToString()
        {
            return String.Format("Node {0}", _name);
        }

        public void Reset()
        {
            _inputs.Clear();
        }

        public void SetName(String name)
        {
            _name = name;
        }

        protected List<LogicalNode> GetInputs()
        {
            return _inputs;
        }

        public void AddInput(LogicalNode node)
        {
            _inputs.Add(node);
        }

        protected virtual bool ComputeOutputInternal()
        {
            return false;
        }

        public bool ComputeOutput()
        {
           // Console.WriteLine("Computing output on {0}.", _name);
            return ComputeOutputInternal();
        }
    }

    public class LogicalInput : LogicalNode
    {
        private bool _state = true;

        public void SetState(bool state)
        {
            _state = state;
        }

        public bool GetState() { return _state; }

        protected override bool ComputeOutputInternal()
        {
            return _state;
        }
    }

    public class LogicalAND : LogicalNode
    {
        protected override bool ComputeOutputInternal()
        {
            List<LogicalNode> inputs = GetInputs();
            bool result = true;
            for (Int32 idx = 0; idx < inputs.Count && result; idx++)
            {
                result = result && inputs[idx].ComputeOutput();
            }
            return result;
        }
    }

    public class LogicalOR : LogicalNode
    {
        protected override bool ComputeOutputInternal()
        {
            List<LogicalNode> inputs = GetInputs();
            bool result = false;
            for (Int32 idx = 0; idx < inputs.Count; idx++)
            {
                result = inputs[idx].ComputeOutput();
                if (result)
                    // If we get one true, that is enough.
                    break;
            }
            return result;
        }
    }

    public class LogicalNOT : LogicalNode
    {
        protected override bool ComputeOutputInternal()
        {
            List<LogicalNode> inputs = GetInputs();
            if (inputs.Count > 0)
            {   // NOTE:  This is not an optimal design for
                // handling distinct different kinds of circuits.
                //
                // It it demonstrative only!!!!
                return !inputs[0].ComputeOutput();
            }
            return false;
        }

然后(快速)测试它:

static void Main(string[] args)
        {
            // The test circuit
            // !((A&&B) || C)
            // A    B   C   Out
            // 1    1   1   0 
            // 1    1   0   0
            // 1    0   1   0
            // 1    0   0   1
            // 0    1   1   0
            // 0    1   0   1
            // 0    0   1   0
            // 0    0   0   1
            // 
            //
            //
            /*     -------     -------
             * A - |     |     |     |
             *     | AND |-----|     |    -------
             * B - | (D) |     |     |    |     |
             *     -------     | OR  |----| NOT |----
             *                 | (E) |    | (F) |
             * C --------------|     |    |     |
             *                 -------    -------
             */

            LogicalInput A = new LogicalInput();
            LogicalInput B = new LogicalInput();
            LogicalInput C = new LogicalInput();
            LogicalAND   D = new LogicalAND();
            LogicalOR    E = new LogicalOR();
            LogicalNOT   F = new LogicalNOT();

            A.SetName("A");
            B.SetName("B");
            C.SetName("C");
            D.SetName("D");
            E.SetName("E");
            F.SetName("F");

            D.AddInput(A);
            D.AddInput(B);

            E.AddInput(D);
            E.AddInput(C);

            F.AddInput(E);

            // Truth Table
            bool[] states = new bool[]{ true, false };
            for(int idxA = 0; idxA < 2; idxA++)
            {
                for(int idxB = 0; idxB < 2; idxB++)
                {
                    for(int idxC = 0; idxC < 2; idxC++)
                    {
                        A.SetState(states[idxA]);
                        B.SetState(states[idxB]);
                        C.SetState(states[idxC]);

                        bool result = F.ComputeOutput();

                        Console.WriteLine("A = {0}, B = {1}, C = {2}, Output = {3}",
                            A.GetState(), B.GetState(), C.GetState(), result.ToString());

                    }
                }
            }
        }
    }

输出:

A = True, B = True, C = True, Output = False
A = True, B = True, C = False, Output = False
A = True, B = False, C = True, Output = False
A = True, B = False, C = False, Output = True
A = False, B = True, C = True, Output = False
A = False, B = True, C = False, Output = True
A = False, B = False, C = True, Output = False
A = False, B = False, C = False, Output = True

这有帮助吗？

关于java - 在java中构建电路模型，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20686896/