expr tree

tree.cc

#include <assert.h>
#include <ctype.h>
#include <stdio.h>
#include <deque>

struct Node
{
  Node(char v) : val(v) {}

  bool isOperator() const
  {
    return !isalnum(val);
  }

  void print() const
  {
    if (isOperator())
    {
      printf("(");
      if (left)
      {
        left->print();
      }
      printf(" %c ", val);
      if (right)
      {
        right->print();
      }
      printf(")");
    }
    else
    {
      printf("%c", val);
    }
  }

  char val;
  Node* left = NULL;
  Node* right = NULL;
};

Node* buildTree(const char* expr)
{
  Node* root = NULL;
  std::deque<Node**> queue;
  queue.push_back(&root);
  for (const char* p = expr; *p; ++p)
  {
    assert(!queue.empty());
    Node** curr = queue.front();
    queue.pop_front();
    assert(*curr == NULL);
    Node* n = new Node(*p);
    *curr = n;
    if (n->isOperator())
    {
      queue.push_back(&n->left);
      queue.push_back(&n->right);
    }
  }
  assert(queue.empty());

  return root;
}

int main(int argc, char* argv[])
{
  Node* root = buildTree(argc > 1 ? argv[1] : "-+a+-abcd");
  root->print();
  printf("\n");
}