12
\$\begingroup\$

I challenge you to write a code to make an (extended) ASCII-art logic gate diagram for the sum of products form of an equation.

Use the following notation to represent gates:

AND
    INPUT───|&&
            |&&───OUTPUT
    INPUT───|&&
OR
    INPUT───|OR
            |OR───OUTPUT
    INPUT───|OR  
Gates with more than 2 inputs
    INPUT───|OR
            |OR
    INPUT───|OR───OUTPUT
            |OR
    INPUT───|OR
NOT
    INPUT───│>o───OUTPUT

Character set

Note that is not an ASCII pipe sign but a box-drawing character. Use box-drawing characters such as ─ │ ┌ ┐ └ ┘ for connections.

Example

Input
    A'*B'+B*C
Output
    A────│>o────│&&
                │&&─────┐
    B────│>o────│&&     └│OR
                         │OR─────A*B+B*C
    B───────────│&&     ┌│OR
                │&&─────┘
    C───────────│&&    

Winner

The winner is the answer with the most up-votes in 5 days

\$\endgroup\$
15
  • 1
    \$\begingroup\$ There are only 95 printable ASCII characters, and they don't include any of these: ─ │ ┌ ┐ └ ┘. I think you're referring to the MS-DOS character set. Also, shouldn't your example have a single B input split between the two AND gates? And can we assume that there will be no need for wires to cross over anywhere? \$\endgroup\$
    – r3mainer
    Mar 4, 2014 at 13:26
  • 2
    \$\begingroup\$ I love how you say "STRICTLY an ASCII art" and require us to use a non-ASCII character set. \$\endgroup\$ Mar 4, 2014 at 13:30
  • \$\begingroup\$ @squeamishossifrage I think there are 128 ASCII characters and 256 after extension of ascii chart visit here juniper.net/techpubs/en_US/idp5.1/topics/reference/general/… \$\endgroup\$ Mar 4, 2014 at 13:34
  • \$\begingroup\$ @squeamishossifrage: No, he refers to some Extended ASCII characters. I've edited the question to clarify that. Extended ASCII includes all seven-bit ASCII characters, as well as some other characters. \$\endgroup\$
    – ProgramFOX
    Mar 4, 2014 at 13:42
  • 1
    \$\begingroup\$ Given the requirement to use box-drawing characters, it seems odd that you're making connections as ─│ rather than ─┤. \$\endgroup\$ Mar 4, 2014 at 15:20

2 Answers 2

16
\$\begingroup\$

C++11

Done at last. And it only took me most of the day.

Before I list the code and sample output, some quick notes:

Things this program does support

  • Any number of terms, each with any number of inputs
  • Reusing inputs
  • Omitting AND/OR gate representation when only one input would be present
  • Use of both codepage 437 line-drawing characters and 7-bit ASCII-friendly characters (use -DCP437 or whatever your compiler's equivalent is for codepage 437 support)

Things this program does not support

  • Grouping with parentheses (because, seriously?)
  • Multiple NOTing
  • Any whitespace that isn't a plain ASCII space
  • Proper golfification (although I did remove all the comments in spirit)
  • Sane coding practices
  • Making eye contact with the input parsing code
  • Portable, Unicode line-drawing characters. I couldn't support Unicode because the rendering logic relies on being able to draw "down" a two-dimensional char buffer.

Code

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <stdexcept>
#include <set>
#include <map>
#include <valarray>
#include <cmath>

using namespace std;

vector<string> split(const string str, const string delim)
{
    vector<string> v;

    set<char> d;
    for (char c : delim) d.insert(c);

    string current {};
    for (char c : str)
    {
        if (d.find(c) != d.end())
        {
            v.push_back(current);
            current = "";
        }
        else
        {
            current += c;
        }
    }
    v.push_back(current);

    return v;
}

using Input = string;
struct TermInput
{
    Input name;
    int ypos;
    bool neg;
};
using Term = vector<TermInput>;
using Expr = vector<Term>;

#ifdef CP437
constexpr char VERT    = '\xB3';
constexpr char HORIZ   = '\xC4';
constexpr char RBRANCH = '\xC3';
constexpr char LUP     = '\xD9';
constexpr char LDOWN   = '\xBF';
constexpr char RUP     = '\xC0';
constexpr char RDOWN   = '\xDA';
#else
constexpr char VERT    = '|';
constexpr char HORIZ   = '-';
constexpr char RBRANCH = '}';
constexpr char LUP     = '\'';
constexpr char LDOWN   = '.';
constexpr char RUP     = '`';
constexpr char RDOWN   = ',';
#endif

string repeat(string s, int n)
{
    stringstream ss;
    for (int i = 0; i < n; i++)
    {
        ss << s;
    }

    return ss.str();
}
string repeat(char c, int n)
{
    stringstream ss;
    for (int i = 0; i < n; i++)
    {
        ss << c;
    }

    return ss.str();
}

enum class Direction
{
    RIGHT,
    DOWN
};

void matrixPut(char *matrix, int h, int w, int x, int y, const string s, Direction dir)
{
    if (x >= w || y >= h)
    {
        stringstream ss;
        ss << "matrixPut: point (" << x << ", " << y << ") out of matrix bounds!";
        throw new out_of_range(ss.str());
    }

    char *ins = matrix + (y * w) + x;
    char *end = matrix + (h * w);
    for (char c : s)
    {
        if (ins >= end) break;
        *ins = c;

        if (dir==Direction::RIGHT)
        {
            ins++;
        }
        else
        {
            ins += w;
        }
    }
}

void matrixPrint(char *matrix, int h, int w)
{
    for (int i = 0; i < (h * w); i++)
    {
        cout << matrix[i];
        if ((i+1)%w == 0) cout << endl;
    }
}

int main (int argc, char *argv[])
{
    string expression;

    if (argc == 1)
    {
        cout << "Enter expression:" << endl;
        getline(cin, expression);
    }
    else
    {
        expression = argv[1];
    }

    expression.erase(remove(expression.begin(), expression.end(), ' '), expression.end());

    Expr expr {};
    auto inputs = set<Input>();
    auto termInputs = multimap<Input, TermInput>();

    int inputYPos = 0;

    auto e = split(expression, "+");
    for (string term : e)
    {
        Term currTerm {};

        auto t = split(term, "*");
        for (string in : t)
        {
            bool neg = false;
            if (in.back() == '\'')
            {
                in.pop_back();
                neg = true;
            }

            Input currInput {in};
            inputs.insert(currInput);

            TermInput ti {currInput, inputYPos, neg};
            currTerm.push_back(ti);

            termInputs.insert(pair<Input, TermInput>{in, ti});
            inputYPos++;
        }

        expr.push_back(currTerm);
        inputYPos++;
    }


    int height = inputs.size() + termInputs.size() + expr.size() - 1;

    int width = 0;

    width += max_element(inputs.begin(), inputs.end(), [](Input a, Input b){ return a.length() < b.length(); })->length() + 2;
    int inputWidth = width;
    width += inputs.size()*2;

    int notAndStart = width;

    width += 7;
    width += expr.size()+1;

    int orStart = width;

    width += 4;

    width += 4;

    width += expression.length();

    char matrix[height * width];
    for (int i = 0; i < height*width; i++) matrix[i] = ' ';
    
    int  baseY = inputs.size();

    {
        int x = width - 4 - expression.length();
        int y = baseY + ((height-baseY) / 2);
        matrixPut(matrix, height, width, x, y, repeat(HORIZ, 4) + expression, Direction::RIGHT);
    }

    {
        int x = orStart;
        int y = baseY + (height-baseY)/2 - expr.size()/2;

        if (expr.size() == 1)
        {
            matrixPut(matrix, height, width, x, y, repeat(HORIZ, 4), Direction::RIGHT);
        }
        else {
            matrixPut(matrix, height, width, x  , y, repeat(HORIZ, expr.size()), Direction::DOWN);
            matrixPut(matrix, height, width, x+1, y, repeat(VERT , expr.size()), Direction::DOWN);
            matrixPut(matrix, height, width, x+2, y, repeat('O'  , expr.size()), Direction::DOWN);
            matrixPut(matrix, height, width, x+3, y, repeat('R'  , expr.size()), Direction::DOWN);
        }
    }

    {
        int x = notAndStart;
        int y = baseY;
        for (Term t : expr)
        {
            string layer[7];
            for (TermInput ti : t)
            {
                layer[0] += HORIZ;
                layer[1] += (ti.neg ? '>' : HORIZ);
                layer[2] += (ti.neg ? 'o' : HORIZ);
                layer[3] += HORIZ;
                layer[4] += (t.size() > 1 ? VERT : HORIZ);
                layer[5] += (t.size() > 1 ? '&' : HORIZ);
                layer[6] += (t.size() > 1 ? '&' : HORIZ);
            }

            for (int i = 0; i < 7; i++)
            {
                matrixPut(matrix, height, width, x+i, y, layer[i], Direction::DOWN);
            }

            y += t.size() + 1;
        }
    }

    {
        int x = 0;
        int y = 0;

        for (Input i : inputs)
        {
            string str = i + ": ";
            str += repeat(HORIZ, inputWidth - str.length());

            matrixPut(matrix, height, width, x, y, str, Direction::RIGHT);
            
            y++;
        }
    }

    {
        int x = inputWidth;
        int num = 0;
        int offset = inputs.size() * 2 - 1;

        for (Input in : inputs)
        {
            int y = 0;
            int len = inputs.size() * 2 - 1;
            auto it = inputs.find(in);
            while (it != inputs.begin())
            {
                it--;
                y++;
                len -= 2;
            }
            matrixPut(matrix, height, width, x, y, repeat(HORIZ, len) + LDOWN, Direction::RIGHT);
        }

        for (Input in : inputs)
        {
            auto yBreakRange = termInputs.equal_range(in);
            valarray<int> yBreaks(termInputs.count(in));
            int idx = 0;
            for (auto ti = yBreakRange.first; ti != yBreakRange.second; ti++)
            {
                yBreaks[idx++] = baseY + ti->second.ypos;
            }

            for (int y : yBreaks)
            {
                matrixPut(matrix, height, width, x+offset, y, repeat(HORIZ, inputs.size()*2 - offset), Direction::RIGHT);
            }

            int y = num + 1;
            int maxBreak = yBreaks.max();
            string branch = repeat(VERT, maxBreak - y + 1);

            for (int i : yBreaks)
            {
                branch[i-y] = RBRANCH;
            }
            branch.back() = RUP;

            matrixPut(matrix, height, width, x+offset, y, branch, Direction::DOWN);

            offset -= 2;
            num++;
        }
    }
    
    {
        int x = notAndStart + 7;
        int outY = baseY + (height-baseY)/2 - expr.size()/2;
        int breakx = expr.size()/2;

        for (Term t : expr)
        {
            int inY = baseY + (t.front().ypos + t.back().ypos) / 2;
            
            matrixPut(matrix, height, width, x, inY, repeat(HORIZ, abs(breakx)+1), Direction::RIGHT);
            
            matrixPut(matrix, height, width, x+abs(breakx)+1, outY, repeat(HORIZ, expr.size()-abs(breakx)), Direction::RIGHT);
            
            if (inY < outY)
            {
                string branch = LDOWN + repeat(VERT, outY-inY-1) + RUP;
                matrixPut(matrix, height, width, x+abs(breakx)+1, inY, branch, Direction::DOWN);
            }
            else if (inY > outY)
            {
                string branch = RDOWN + repeat(VERT, inY-outY-1) + LUP;
                matrixPut(matrix, height, width, x+abs(breakx)+1, outY, branch, Direction::DOWN);
            }
            
            outY++;
            breakx--;
        }
    }

    cout << endl;
    matrixPrint(matrix, height, width);
    cout << endl;
}

Sample output

$ ./gates "A'*B'+B*C"

A: -----.
B: ---. |
C: -. | |
    | | `->o-|&&--.
    | }--->o-|&&  `-|OR
    | |          ,--|OR----A'*B'+B*C
    | `------|&&-'
    `--------|&&

$ ./gates "A*B'*C+B*D'+F*C'*D+G*E*A'+F"

A: -------------.
B: -----------. |
C: ---------. | |
D: -------. | | |
E: -----. | | | |
F: ---. | | | | |
G: -. | | | | | |
    | | | | | | }----|&&
    | | | | | }--->o-|&&---.
    | | | | }--------|&&   |
    | | | | | | |          |
    | | | | | `------|&&--.|
    | | | }------->o-|&&  ||
    | | | | |   |         |`---|OR
    | }--------------|&&  `----|OR
    | | | | `----->o-|&&-------|OR----A*B'*C+B*D'+F*C'*D+G*E*A'+F
    | | | `----------|&&  ,----|OR
    | | |       |         |,---|OR
    `----------------|&&  ||
      | `------------|&&--'|
      |         `->o-|&&   |
      |                    |
      `--------------------'

Sample output (with CP437 enabled)

A: ─────────────┐
B: ───────────┐ │
C: ─────────┐ │ │
D: ───────┐ │ │ │
E: ─────┐ │ │ │ │
F: ───┐ │ │ │ │ │
G: ─┐ │ │ │ │ │ │
    │ │ │ │ │ │ ├────│&&
    │ │ │ │ │ ├───>o─│&&───┐
    │ │ │ │ ├────────│&&   │
    │ │ │ │ │ │ │          │
    │ │ │ │ │ └──────│&&──┐│
    │ │ │ ├───────>o─│&&  ││
    │ │ │ │ │   │         │└───│OR
    │ ├──────────────│&&  └────│OR
    │ │ │ │ └─────>o─│&&───────│OR────A*B'*C+B*D'+F*C'*D+G*E*A'+F
    │ │ │ └──────────│&&  ┌────│OR
    │ │ │       │         │┌───│OR
    └────────────────│&&  ││
      │ └────────────│&&──┘│
      │         └─>o─│&&   │
      │                    │
      └────────────────────┘
\$\endgroup\$
6
  • 4
    \$\begingroup\$ +10 for sheer dogged determination :-) \$\endgroup\$
    – r3mainer
    Mar 5, 2014 at 11:33
  • \$\begingroup\$ That is not the output I wanted but, +1 for your hard-work(personally, I appreciate it).Also mention your language! \$\endgroup\$ Mar 5, 2014 at 17:07
  • \$\begingroup\$ Kudos. This is very nice, CP437 or not. \$\endgroup\$ Mar 5, 2014 at 22:52
  • \$\begingroup\$ I made a few edits to the post (not the code) based on the feedback above. I also got MinGW to work on my system so I could build it with native CP437 support, so I added some sample output form that. \$\endgroup\$
    – curtmack
    Mar 6, 2014 at 8:43
  • \$\begingroup\$ On line 202 I get a compiling error in VisualExpress: int height and int width: Expression must have a constant value. Also you were missing #include <vector> \$\endgroup\$
    – Jack Cole
    Apr 22, 2016 at 20:44
5
\$\begingroup\$

C++

Whew ! Done in 1 day 12 hrs!!!
This code handles array only

INPUT (TYPES)

  • Only SOP(sum of products) form.
  • Only addition of terms with two variables multiplying

    EXAMPLES :-
    
        A*B'+B*A+C*D  
    
        X*Y+Z'*A'*V*D+B*G+C'*A'  
    
  • Can handle any number of terms,variables.

    CODE :-

    #include<iostream>
    using namespace std;
    int main()
    {
    int i,j,k,l,m=0;
    char arr[80][80],expr[45];
    cout<<"enter the SOP(Sum Of products) expression : ";
    cin>>expr;
    cout<<"\n\n";
    for(i=0;expr[i]!='\0';i++)
    if(expr[i]=='*')m++;
    for(i=0;i<80;i++)
        for(j=0;j<80;j++)
            arr[i][j]=' ';
    for(i=0,j=0;i<80,expr[j]!='\0';j++)
    {
        if(expr[j]<=90&&expr[j]>=65||expr[j]<=122&&expr[j]>=97)
        {
            arr[i][0]=expr[j];
            i+=2;
        }
    }
    for(i=0,j=1;i<80;j++)
    {
        if(j==80){i++;j=0;}
        if(arr[i][j-1]<=90&&arr[i][j-1]>=65||arr[i][j-1]<=122&&arr[i][j-1]>=97)
        {
            for(k=0;k<7;k++)
                arr[i][j+k]=196;
            arr[i][j+k]=180;
        }
    }
    for(i=0,j=0;i<80;j++)
    {
        if(j==80){i++;j=0;}
        if(arr[i][j]==(char)180&&arr[i][j+1]==' ')
        {
            arr[i][j+1]=38;
        }
    }
    for(i=0,j=0,k=1;i<80;j++)
    {
        if(j==80){i++;j=0;}
        if(arr[i-1][j]==(char)180&&arr[i+1][j]==(char)180)
        {
            if(arr[i-1][j+1]==(char)38&&arr[i+1][j+1]==(char)38&&k)
            {
                arr[i][j]=179;arr[i][j+1]=38;
                for(l=2;l<4;l++)
                {
                    arr[i][j+l]=196;
                }
                k--;
            }
            else if(k==0)
            {
                k=1;
            }
        }
    }
    l=m;
    for(i=0,j=0;i<80;j++)
    {
        if(j==80){i++;j=0;}
        if(arr[i][j-1]==(char)196&&arr[i][j+1]==' '&&arr[i][j-2]==(char)38)
            {
            if(arr[i+3][j-2]==(char)38)
            {
                for(k=0;k<l;k++)
                    arr[i][j+k]=(char)196;
                arr[i][j+k-1]=(char)191;
    
                l--;
            }
            else
            {
                for(k=0;k<m;k++)
                arr[i][j+k]=(char)196;
            }
        }
    }
    for(i=0,j=0,k=1;i<80;j++)
    {
        if(j==80){i++;j=0;}
        if(arr[i][j]==(char)191&&arr[i][j-1]==(char)196)
        {
            for(;arr[i+k][j]==' ';k++)
            {
                arr[i+k][j]=(char)179;
            }
        k=1;
        }
    }
    for(i=0,j=0;i<80;j++)
    {
        if(j==80){i++;j=0;}
        if(arr[i][j]==(char)179&&arr[i][j-3]==(char)38&&arr[i+1][j]==(char)196)
        {
            arr[i][j]=(char)192;
            for(k=1;arr[i-k][j+k]==(char)179;k++)
            {
                arr[i-k][j+k]=(char)192;
            }
        }
    }
    for(i=0,j=0;i<80;j++)
    {
        if(j==80){i++;j=0;}
        if(arr[i][j-1]==(char)192)
        {
            for(k=0;arr[i][j+k]!=' ';k++)
                arr[i][j+k]=(char)196;
        }
    }
    for(i=0,j=0;i<80;j++)
    {
        if(j==80){i++;j=0;}
        if(arr[i][j-1]==(char)192&&arr[i][j]==' '||arr[i][j-1]==(char)196&&arr[i][j]==' ')
        {
            arr[i][j]=(char)180;
            arr[i][j+1]='O';
            arr[i][j+2]='R';
        }
    }
    for(i=0,j=0;i<80;j++)
    {
        if(j==80){i++;j=0;}
        if(arr[i][j-1]=='R'&&arr[i+1][j-1]==' ')
        {
            for(k=0;k<3;k++)
                arr[i][j+k]=(char)196;
            j+=k;
            for(k=0;expr[k]!='\0';k++)
            {
                arr[i][j+k]=expr[k];
            }
        }
    }
    for(i=0,k=0;i<80,expr[k]!='\0';k++)
    {
        if((expr[k]<='z'&&expr[k]>='a'||expr[k]<='Z'&&expr[k]>='A'))
        {
            if(expr[k+1]=='\'')
                arr[i][1]='\'';
            i+=2;
        }
    }
    for(i=0,j=0;i<80;j++)
    {
        if(j==80){i++;j=0;}
        if(arr[i][j]=='\''&&arr[i][j+1]==(char)196)
        {
            arr[i][j+3]=(char)180;
            arr[i][j+4]=(char)62;
            arr[i][j+5]='o';
        }
    }
    for(i=0;i<35;i++)
    {
        for(j=0;j<80;j++)
            cout<<arr[i][j];
        cout<<'\n';
    }
    return 0;
    }  
    

OUTPUT

enter image description here

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.