Graph after reading a file text

Pages: 12
Do you know Verilog?
I have to make a simulator, I made class for logic elements and now I don't know how to implement the graph. Considering a line:
z= a or b

After I read 'z=', I don't know to create a port taking address of a and b.
Moreover, if line is:

z= (a or b ) and (c and (d or f))

How can I implement this graph?
OR and AND are binary operators. Think of a (binary) tree. Tree is a graph.
   and
 or   and
a  b c   or
        d  f
Never used Verilog, and I barely remember VHDL, but it sounds like this link might help you:
https://www.doulos.com/knowhow/verilog_designers_guide/a_simple_design/
1
2
3
4
5
// Verilog code for AND-OR-INVERT gate
module AOI (input A, B, C, D, output F);
  assign F = ~((A & B) | (C & D));
endmodule
// end of Verilog code 


Actually I think I misunderstood what you were asking. Yes, if you want to implement this your self, build a tree.
Shunting yard algorithm might be of use.
Last edited on
I don't know how to read the line and so build this binary tree.
Can you help me?
what line? 'the line' ? Can you use more words to explain what you have, and what you want?
Ok. I read file word by word, when I find 'z=' I have to build a graph of logic ports (I have a class of logic ports) reading all the line after 'z='.
I have to build a graph as the one suggested by keskiverto, but I don't know how to do.

P.s. logic ports class has two (or 1 if it's a not port) pointers to other logic ports.
I assume ema means the original line, e.g.
z= (a or b ) and (c and (d or f))
or, as a start, z= a or b.

It sounds this has less to do with Verilog itself and more so just how to build an expression tree for logic gates.

As I said earlier, I suggest doing something akin to the shunting yard algorithm.
Start with the simpler equation first: a or b.
But for the more complicated equation, you would split it up into its tokens
e.g. { (, a, or, b, ), and, (, c, and, (, d, or, f, ), ) }

Then, you start to apply (a modified, perhaps simpler, version of) the shunting-yard algorithm
https://en.wikipedia.org/wiki/Shunting-yard_algorithm

This will transform your equation as you see fit into reverse-Polish notation, and from there you can combine both binary operands as children of the operator parent. (Or, you could modify it to directly build the tree, I suppose.)
e.g.
For a or b, you push a, push b, and then once you see an operator, you consume the operator and pop-off the previous two tokens.
So, a or b becomes a, b, or, and basically:
- first operand becomes left child
- second operator become right leaf
- operator (or) becomes parent leaf.

I'm probably not explaining it the best, it takes some care to make sure you get it right with parentheses; I do suggest reading the Wikipedia article or searching for other articles on mathematical expression trees.
Last edited on
An alternative to the shunting yard algo:
https://en.wikipedia.org/wiki/Recursive_descent_parser
Last edited on
I have understood quite well the algorithm, but it's not clear for me how can use it in c++ to build a binary tree with logic ports...
Polymorphism, composite pattern:
https://en.wikipedia.org/wiki/Composite_pattern
Sounds like he wants someone to do it for him.
dutch, I'm not asking the code done. I'm in difficult and I'm just looking for a help.
I made class for logic elements
Let's start there. Can you show us your class?
Last edited on
I made class but there are about 300 lines of code, but I cane resume:
class Component has many methods, 1 or 2 pointers to Component, bool state.
state is given by logic function of elements: for example, if component is a And gate, state is given by:
 
_state=_pointer_1.getState() && _pointer_2.getState();

Now I have implemented Shunting yard algorithm, so I have a post-order view of a binary tree.
Which is the best way to implement this tree?
Imagine i have:
1
2
3
4
5
6
7
8
 i=0;
 string line="a or b and not c or d"
 queue<string> output_queue;
 void shunting_yard(line, output_queue);
 while(i<output_queue.size()){
        cout<<output_queue[i]<<",";
        i++;
}

and output is:
a,b,or,c,not,and,d,or,
where a,b,c,d are input of my circuit.
Moreover, I have a vector<element> where:
1
2
3
4
struct element{
    string name_of_input;
    Component* node;
}

After a check, I have access to field node of vector.
How I implement the tree?
Finally you've actually shown some work!
Here's a simplistic example:

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
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>

struct Node {
    std::string data;
    Node *left, *right;
    Node(std::string s) : data{s}, left{}, right{} {}
};

Node *build_tree(const std::vector<std::string>& v, size_t& i) {
    if (i == 0)
        return nullptr;
    const std::string& s = v[i - 1];
    Node *nd = new Node(v[i - 1]);
    if (s == "and" || s == "or") {
        nd->left = build_tree(v, --i);
        nd->right = build_tree(v, --i);
    }
    else if (s == "not")
        nd->left = build_tree(v, --i);
    return nd;
}

void print(const Node *nd, int tab = 0) {
    if (!nd) return;
    std::cout << std::setw(tab * 4) << "" << nd->data << '\n';
    print(nd->left,  tab + 1);
    print(nd->right, tab + 1);
}

int main() {
    std::vector<std::string> v
        { "a","b","or","c","not","and","d","or" };
    size_t i = v.size();
    Node *root = build_tree(v, i);
    print(root);
    // not bothering to delete the tree
}

or
    d
    and
        not
            c
        or
            b
            a
Last edited on
If I try:
 
Not *gate = new Not;


I receive error: invalid new-expression of abstract class type 'Not'
You can't instantiate objects that have abstract type, because that type (intentionally) lacks implementation for some of its member functions. You can't call functions that have no implementation.
I made class but there are about 300 lines of code, but I cane resume:
class Component has many methods, 1 or 2 pointers to Component, bool state.
state is given by logic function of elements: for example, if component is a And gate, state is given by:
_state=_pointer_1.getState() && _pointer_2.getState();

Why is it so hard to show us the actual declarations for your class? If you have 300 lines of code in the class declaration then edit out the code and leave just the declarations.


If I try:
Not *gate = new Not;
I receive error: invalid new-expression of abstract class type 'Not'
This is a perfect example of why you need to show the class. Every one of us responding on this thread knows what's causing this problem and would have caught it before you even ran into it.
OK, time’s up on this one. It’s been going on for 5 days. That’s far too long. Go back to the books. Green tick and move 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
44
45
template <typename T> 
class Component {
public:
    Component();
    virtual ~Component();
    virtual void logicFunction()=0;
    void setInputs(const Component &);
    T getOutput() const;
    virtual void setState(bool&)=0;
 protected:
    T  _present_state,_previous_state;
    Component<T> *_x1;
    float _lh,_hl;
private:
};

template <typename T>
class Not : public Component<T>{
    using Component<T>::_x1;
    using Component<T>::_present_state;
    using Component<T>::_previous_state;
public:
    Not();
    virtual ~Not();
    void logicFunction();

protected:

private:
} ;

template <typename T>
Not<T> :: Not() {
    *_x1= nullptr;
}
template <typename T>
Not<T> :: ~Not() {
}
template <typename T>
void Not<T> ::logicFunction() {
    _previous_state=_present_state;
    if (_x1->getOutput()=='x') _present_state='x';
    else _present_state=!_x1.getOutput();
}

One more question: I included class Component in an .hpp file because of the template.
Now I want to make class Circuit that has pointers to class Component<T>.
Do I have to put class Circuit in a .hpp, too?
Last edited on
Pages: 12