gate problem

"how to take input in this case to solve this circuit"


electrical circuit is in a form of full bin tree. all inputs are provided at the l nodes and every other node is a logic gate

given n in first line
second line consists of space separated binary numbers
and next n-1 lines consists of logic gate space separated

Last edited on
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
using namespace std;

int main()
{
   map<string,bool (*)(int,int)> M{ { "xor" , []( int a, int b ){ return a + b == 1; } },
                                    { "and" , []( int a, int b ){ return a + b == 2; } },
                                    { "nand", []( int a, int b ){ return a + b <= 1; } },
                                    { "or"  , []( int a, int b ){ return a + b >= 1; } },
                                    { "nor" , []( int a, int b ){ return a + b == 0; } },
                                    { "xnor", []( int a, int b ){ return a == b    ; } } };

   istringstream in( "4               \n"
                     "1 1 0 1 1 0 0 0 \n"
                     "xor nand or and \n"
                     "or nor          \n"
                     "xnor            \n" );
   int n;
   in >> n;

   int nodes = 1 << ( n - 1 );

   vector<int> X( nodes);
   for ( int &e : X ) in >> e;

   for ( nodes /= 2; nodes; nodes /= 2 )
   {
      for ( int i = 0; i < nodes; i++ )
      {
         string op;
         in >> op;
         X[i] = M[op]( X[2*i], X[2*i+1] );
      }
      X.resize( nodes );
//    for ( auto e : X ) cout << e << ' ';   cout << '\n';
   }
   cout << X[0] << '\n';
}
Electricals circuit are generally graphs, not trees. But a single non-self referencing logical expression is a tree, which what I think the question is about.

In this case, since it's a full binary tree, so this actually makes it easier to streamline.

You're given n = 4.
So (it looks like) you know you have n*2 = 8 inputs.

You can do this with
1
2
3
4
5
6
7
8
9
10
11
#include <vector>

// ...

int n;
cin >> n;
vector<int> inputs(2*n);
for (int i = 0; i < 2*n; i++)
{
    cin >> inputs[i];
}


So now, you have all the inputs stored.
Next, you know that you now have n logic gates, and n - 1 lines left.
So, loop over the n gates on the first loop.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int i = 0; i < n; i++)
{
    string gate;
    cin >> gate;

    if (gate == "xor")
    {
        inputs[i] = inputs[2*i] ^ inputs[2*i+1];
    }
    else if (gate == "nand")
    {
        inputs[i] = ~(inputs[2*i] & inputs[2*i+1]);
    }
}


You'd do this loop n-1 times, halving the inputs needed each time.
e.g. loop over n/2 inputs on the second line.
(You'll probably end up having a loop within a loop)

Try something out, then ask for more help and show what you've tried.
(or copy lastchance's code)
Last edited on
And here's a functional approach, for completeness:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// logic_gates.d

void main() {

    import std;

    bool function(bool, bool)[string] funs = [
          "or" : (a, b) =>  (a | b),
         "nor" : (a, b) => !(a | b),
         "xor" : (a, b) =>  (a ^ b),
        "xnor" : (a, b) => !(a ^ b),         
         "and" : (a, b) =>  (a & b),
        "nand" : (a, b) => !(a & b),
    ];

    auto lines = File("input.txt").byLine.drop(1);
    // auto lines = stdin.byLine.drop(1);

    auto data = lines.front.splitter(' ')
        .map!"a.to!int.to!bool".array;

    foreach (line; lines.drop(1)) {
        zip(
            line.splitter(' '),     // op
            data.stride(2),         // evens
            data.drop(1).stride(2)  // odds
        ).map!(
            z => funs[z[0]](z[1], z[2])
        ).copy(data);        
    }

    data[0].to!int.writeln;
}

Last edited on
Topic archived. No new replies allowed.