rpn.c

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

char *input;

typedef enum {
  Num,
  Op
} Kind;

typedef struct Node {
  Kind kind;
  union {
    int num;
    struct {
      struct Node *lhs, *rhs;
      char op;
    } op;
  } body;
} Node;

Node *node_num(int num) {
  Node *node = malloc(sizeof(Node));
  node->kind = Num;
  node->body.num = num;
  return node;
}

Node *node_op(char op, Node *lhs, Node *rhs) {
  Node *node = malloc(sizeof(Node));
  node->kind = Op;
  node->body.op.op = op; 
  node->body.op.lhs = lhs; 
  node->body.op.rhs = rhs; 
  return node;
}

void show_node_sub(Node *node, int indent) {
  for (int i = 0; i < indent; i++) putchar(' ');
  switch (node->kind) {
    case Op: {
               printf("%c\n", node->body.op.op);
               show_node_sub(node->body.op.lhs, indent + 1);
               show_node_sub(node->body.op.rhs, indent + 1);
             }
             break;
    case Num: {
                printf("%d\n", node->body.num);
              }
              break;
  }
}

void show_node(Node *node) {
  show_node_sub(node, 0);
}

int eval(Node *node) {
  switch (node->kind) {
    case Op: {
      int lhs = eval(node->body.op.lhs); 
      int rhs = eval(node->body.op.rhs);
      switch (node->body.op.op) {
        case '+': return lhs + rhs;
        case '-': return lhs - rhs;
        case '*': return lhs * rhs;
        case '/': return lhs / rhs;
        default: exit(-1);
      }
    }
    case Num: return node->body.num;
  }
}

Node *parse_num() {
  int num = 0;
  while (*input && isdigit(*input)) 
    num = (*(input++) - '0') + num * 10;
  return node_num(num);
}

Node *parse() {
  Node *stack[1024]; Node **sp = stack;

  while (*input) {
    while (*input && isspace(*input)) input++;
    if (!*input) break;

    if (isdigit(*input)) {
      *(sp++) = parse_num();
      continue;
    }

    char op = *(input++);
    Node *rhs = *(--sp); Node *lhs = *(--sp);
    *(sp++) = node_op(op, lhs, rhs);
  }

  return stack[0];
}

int main() {
  char _input[1024];
  input = _input;

  fgets(input, 1024, stdin);

  Node *node = parse();

  puts("Tree:");
  show_node(node);

  puts("Eval:");
  printf("%d\n", eval(node));

  return 0;
}