list flatten

// listflatten.cpp
//
#include <cctype>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <utility>
using namespace std;

const char lparen = '(';
const char rparen = ')';

struct node {
    bool atomp;
    int  val;
    struct node *sub;
    struct node *next;
};

struct node *
parse(char *str)
{
    if (!*str) return NULL;
    char *p = str;
    while(isspace(*p))
    {
        p++;
    }
    assert(*p == lparen);
    char *q;
    int lcnt = 1;
    for(q=p+1; ; q++)
    {
        if (*q == rparen)
            lcnt--;
        else if (*q == lparen)
            lcnt++;

        if (lcnt == 0)
            break;
    }
    assert(*q == rparen);
    *q = '\0';

    struct node *newnode = (struct node*)malloc(sizeof(struct node));
    for(p++; isspace(*p); p++)
        ;
    int val = 0;
    bool atomp = false;
    if (isdigit(*p))
    {
        atomp = true;
        while(isdigit(*p))
        {
            val = val * 10 + *p-'0';
            p++;
        }
    }
    newnode->atomp = atomp;
    newnode->val   = val;
    newnode->sub   = parse(p);
    newnode->next  = parse(q+1);

    return newnode;
}

typedef pair<struct node*, struct node*> pnn;

pnn flatten(struct node *head)
{
    pnn ret; ret.first=ret.second=NULL;
    if (!head) return ret;

    pnn subpair  = flatten(head->sub);
    pnn nextpair = flatten(head->next);
    head->sub=head->next=NULL;

    struct node dummy;
    struct node *subhead = subpair.first;
    struct node *subtail = subpair.second;
    struct node *nexthead = nextpair.first;
    struct node *nexttail = nextpair.second;
    struct node *tail = &dummy;

    // set up new head
    if (head->atomp) { tail->next=head; tail = tail->next; }
    if (subhead) { tail->next = subhead; tail = subtail; }
    if (nexthead) { tail->next = nexthead; tail = nexttail; }

    if (tail==&dummy) { ret.first=ret.second=NULL; }
    else { ret.first=dummy.next; ret.second=tail; }
    return ret;
}

void print(struct node *head)
{
    if (!head) return;
    cout << "( ";
    if (head->atomp)
        cout << head->val << " ";
    print(head->sub);
    cout << ") ";
    print(head->next);
}


int main()
{
    char list[] = "(1 (21 (339) ()))(410)(()(123))";
    //char list[] = "(1(3 ()))(2)";
    //char list[] = "(())";

    struct node *head = parse(list);
    print(head);
    cout << endl;
    cout << "flatten list\n";
    head = flatten(head).first;
    print(head);
    cout << endl;
}