我最近在一次工作面试中担任Java开发人员。我承担了一项任务:考虑一种用Java表示电路的好方法(例如下图中的电路)。
picture for illustration http://oi40.tinypic.com/nnr4wj.jpgg
电路是逻辑门XOR，AND，OR等的组合。每个门都有两个输入端口和一个输出端口。每个输出都连接到另一个门的输入，该门一直到更高的门(如图所示)。使系统简单，不允许循环(尽管现实生活中的电路可以循环使用)。
我被要求考虑使用以下准则来用Java表示此模型的好方法:
我选择将系统设计成一棵树，面试官告诉我这是一个不错的选择。然后，我构建这些类:
节点
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
这个有帮助吗？