/* rpn.c
 *
 * Takes a string of reverse polish notation math and pretty-prints it with
 * parenthesis. Recognizes the {*, +, -, /} operators and ignores everything
 * else. 
 *
 */

/*
- tree data structure
- read in integer function (std?)

*/

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

#define LINE_LEN  1024

struct rpn_node {
  char val;
  struct rpn_node *left;
  struct rpn_node *right;
}; 

int rpn_parse(char s[], struct rpn_node *node); 
void rpn_print(struct rpn_node *node);
int rpn_eval(struct rpn_node *node);
int isoper(char c);

int main(void) {
  char line[LINE_LEN] = "";
  struct rpn_node root_node;
  char tc;
  int i,j;

  // read string
  fgets(line, LINE_LEN, stdin); 

  // reverse it
  j = strlen(line) - 1;
  for(i = 0; i <= j/2; i++) {
    tc = line[i];
    line[i] = line[j-i];
    line[j-i] = tc;
  }

  // parse it down to single char numbers and opers
  for(i = j = 0; i < strlen(line); i++) {
    if(isdigit(line[i]) || isoper(line[i]))
      line[j++] = line[i];
  }
  line[j] = '\0';
  //printf("Compressed: %s\n", line);
  
  // recursively parse down and store result in right; then recursively parse
  // down and store result in left
  rpn_parse(line, &root_node);

  // spider down the tree to the left, printing
  rpn_print(&root_node);
  printf(" = %d\n", rpn_eval(&root_node));
  return;
  // &new_node = malloc(sizeof(struct node))
}

// returns the number of characters that got chomped up
int rpn_parse(char s[], struct rpn_node *node) {
  int i=0;

  node->val = s[0];
  i++;
  //printf("Got len=%d, isoper=%d: %s\n", (int)strlen(s), isoper(s[0]), s);

  if(isoper(s[0])) {
    //printf("Got an oper: %c\n", s[0]);
    // load up right and left
    node->right = malloc(sizeof(struct rpn_node));
    node->left = malloc(sizeof(struct rpn_node));
    i += rpn_parse(&s[i], node->right);
    i += rpn_parse(&s[i], node->left);
  }
  return i;
}

void rpn_print(struct rpn_node *node) {
  if(isoper(node->val)) {
    printf("(");
    rpn_print(node->left);
    printf(" %c ", node->val);
    rpn_print(node->right);
    printf(")");
  } else {
    printf("%c", node->val);
  }
}

int isoper(char c) {
  switch(c) {
    case '+':
    case '-':
    case '*':
    case '/':
      return 1;
      break;
    default:
      return 0;
  }
}

int rpn_eval(struct rpn_node *node) {
  if(isdigit(node->val)) {
    return node->val - '0';
  } 
  switch(node->val) {
    case '+':
      return rpn_eval(node->left) + rpn_eval(node->right);
    case '-':
      return rpn_eval(node->left) - rpn_eval(node->right);
    case '*':
      return rpn_eval(node->left) * rpn_eval(node->right);
    case '/':
      return rpn_eval(node->left) / rpn_eval(node->right);
    default:
      printf("ERROR: unexpected character '%c'.", node->val);
      exit(-1);
  }
}