backup of stuffsHEADmaster

1 files changed, 129 insertions, 0 deletions

diff --git a/rpn.c b/rpn.c
new file mode 100644
index 0000000..d1c72ad
--- /dev/null
+++ b/rpn.c
@@ -0,0 +1,129 @@
+/* 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);
+  }
+}