Простой рекурсивный спуск

#include <stdio.h>
#include <stdlib.h>

struct Node {
  enum { VAR, INT, OP } type;
  union {
    char var;
    int value;
    struct {
      char op;
      Node *left;
      Node *right;
    } node;
  };
};

typedef const char *string;

Node *expr(string& str);

// factor = n | d | (expr).
Node *factor(string& str) {
  if ('0' <= *str && *str <= '9') {
    Node *digit = new Node;
    digit->type = Node::INT;
    digit->value = *str - '0';
    ++str;
    return digit;
  } else if ('a' <= *str && *str <= 'z') {
    Node *var = new Node;
    var->type = Node::VAR;
    var->var = *str;
    ++str;
    return var;
  } else if (*str == '(') {
    ++str;
    Node *subexpr = expr(str);
    if (*str != ')') {
      printf("unbalanced bracket\n");
      exit(1);
    }
    ++str;
    return subexpr;
  } else {
    printf("unknown symbol %c\n", *str);
    exit(1);
  }
}

// term = factor { (*|/) factor }.
Node *term(string& str) {
  Node *res = factor(str);
  while (*str == '*' || *str == '/') {
    Node *mul = new Node;
    mul->type = Node::OP;
    mul->node.op = *str;
    mul->node.left = res;
    ++str;
    mul->node.right = factor(str);
    res = mul;
  }
  return res;
}

// expr = term { (+|-) term }.
Node *expr(string& str) {
  Node *res = term(str);
  while (*str == '+' || *str == '-') {
    Node *summ = new Node;
    summ->type = Node::OP;
    summ->node.op = *str;
    summ->node.left = res;
    ++str;
    summ->node.right = term(str);
    res = summ;
  }
  return res;
}

void indent(int n) {
  for(int i = 0; i < n; ++i) {
    printf("  ");
  }
}

void print_tree(Node *node, int depth) {
  switch (node->type) {
    case Node::VAR:
      indent(depth);
      printf("variable %c\n", node->var);
      break;
    case Node::INT:
      indent(depth);
      printf("value %d\n", node->value);
      break;
    case Node::OP:
      indent(depth);
      printf("Node %c {\n", node->node.op);
      print_tree(node->node.left, depth + 1);
      print_tree(node->node.right, depth + 1);
      indent(depth);
      printf("}\n");
      break;
  }
}

int main(int argc, char *argv[]) {
  if (argc < 2) {
    printf("bad parameter\n");
    return 1;
  }

  const char *input = argv[1];
  Node *n = expr(input);
  print_tree(n, 0);
  return 0;
}