Solution to Parse Tree (Codeforces Gym 100357K)

parse tree.cpp

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string s;
int priority(char c)
{
    if (c=='+'||c=='-')
        return 1;
    if (c=='*'||c=='/')
        return 2;
    if (c=='^')
        return 3;
    return -1;
}
const int leaf=1,bra=2;
int cnt;
vector<vector<char>> mp;
struct node;
extern node tree[401];
struct node
{
    char ch;
    int w,h,type,le,ri;
    node():ch(),w(),h(),type(),le(),ri(){}
    void parse(int l,int r)
    {
        if (l==r)
        {
            type=leaf;
            ch=s[l];
            w=h=1;
            return;
        }
        int curidx=-1,brac=0;
        for (int i=r;i>=l;--i)
        {
            if (s[i]==')')
                ++brac;
            else if (s[i]=='(')
                --brac;
            else if (!brac&&s[i]!='^'&&priority(s[i])!=-1&&(curidx==-1||priority(s[i])<priority(s[curidx])))
                curidx=i;
        }
        if (curidx==-1)
        {
            int i=l;
            brac=0;
            for (;i<=r;++i)
                if (s[i]=='(')
                    ++brac;
                else if (s[i]==')')
                    --brac;
                else if (!brac&&s[i]=='^'&&curidx==-1)
                    break;
            if (i<=r)
                curidx=i;
        }
        if (curidx!=-1)
        {
            ch=s[curidx];
            le=++cnt;
            tree[le].parse(l,curidx-1);
            ri=++cnt;
            tree[ri].parse(curidx+1,r);
            type=bra;
            w=tree[le].w+tree[ri].w+5;
            h=max(tree[le].h,tree[ri].h)+2;
        }
        else if (s[l]=='('&&s[r]==')')
            parse(l+1,r-1);
    }
    int draw(int x,int y)
    {
        if (type==leaf)
        {
            mp[x][y]=ch;
            return y;
        }
        auto c=tree[le].draw(x+2,y);
        mp[x+1][c]='|';
        mp[x][c]='.';
        for (int i=c+1;i<=y+tree[le].w;++i)
            mp[x][i]='-';
        mp[x][y+tree[le].w+1]='[';
        mp[x][y+tree[le].w+2]=ch;
        mp[x][y+tree[le].w+3]=']';
        auto c2=tree[ri].draw(x+2,y+tree[le].w+5);
        mp[x+1][c2]='|';
        for (int i=y+tree[le].w+4;i<c2;++i)
            mp[x][i]='-';
        mp[x][c2]='.';
        return y+tree[le].w+2;
    }
}tree[401];
int main()
{
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    cin>>s;
    tree[0].parse(0,int(s.size())-1);
    mp=vector<vector<char>>(tree[0].h,vector<char>(tree[0].w,' '));
    tree[0].draw(0,0);
    for (auto& r:mp)
    {
        for (auto c:r)
            cout<<c;
        cout<<endl;
    }
    return 0;
}