Advertisement
allancslima

Binary tree from parentheses notation

Dec 15th, 2019
397
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.20 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. typedef struct node {
  6.     int item;
  7.     struct node *next;
  8. } node;
  9.  
  10. typedef struct stack {
  11.     node *top;
  12. } stack;
  13.  
  14. typedef struct binary_tree {
  15.     int item;
  16.     struct binary_tree *left;
  17.     struct binary_tree *right;
  18. } binary_tree;
  19.  
  20. // STACK
  21.  
  22. stack *create_stack()
  23. {
  24.     stack *new_stack = (stack*) malloc(sizeof(stack));
  25.     new_stack->top = NULL;
  26.     return new_stack;
  27. }
  28.  
  29. node* create_node(int item)
  30. {
  31.     node *new_node = (node*) malloc(sizeof(node));
  32.     new_node->item = item;
  33.     new_node->next = NULL;
  34.     return new_node;
  35. }
  36.  
  37. void push(stack *stack, int item)
  38. {
  39.     node *new_node = create_node(item);
  40.     new_node->next = stack->top;
  41.     stack->top = new_node;
  42. }
  43.  
  44. int is_empty(stack *stack)
  45. {
  46.     return stack->top == NULL;
  47. }
  48.  
  49. void pop(stack *stack)
  50. {
  51.     if (is_empty(stack)) {
  52.         printf("Stack underflow\n");
  53.     } else {
  54.         node *top = stack->top;
  55.         stack->top = top->next;
  56.         free(top);
  57.     }
  58. }
  59.  
  60. // BINARY TREE
  61.  
  62. binary_tree* create_binary_tree(int item, binary_tree *left, binary_tree *right)
  63. {
  64.     binary_tree *new_binary_tree = (binary_tree*) malloc(sizeof(binary_tree));
  65.     new_binary_tree->item = item;
  66.     new_binary_tree->left = left;
  67.     new_binary_tree->right = right;
  68.  
  69.     return new_binary_tree;
  70. }
  71.  
  72. int closing_bracket_index(char *string, int begin, int end)
  73. {
  74.     stack *stack = create_stack();
  75.     while (begin <= end) {
  76.         if (string[begin] == '(') {
  77.             push(stack, 1);
  78.         } else if (string[begin] == ')') {
  79.             pop(stack);
  80.             if (is_empty(stack)) {
  81.                 free(stack);
  82.                 return begin;
  83.             }
  84.         }
  85.         begin++;
  86.     }
  87.     return -1;
  88. }
  89.  
  90. binary_tree* binary_tree_from_string(char *string, int begin, int end)
  91. {
  92.     if (begin >= end) return NULL;
  93.  
  94.     char number[11];
  95.     int len = 0;
  96.    
  97.     while (string[begin] >= 48 && string[begin] <= 57) {
  98.         number[len++] = string[begin];
  99.         begin++;
  100.     }
  101.     number[len] = '\0';
  102.     if (strlen(number) == 0) return NULL;
  103.  
  104.     int value = atoi(number);
  105.     binary_tree *bt = create_binary_tree(value, NULL, NULL);
  106.  
  107.     int closing_index = closing_bracket_index(string, begin, end);
  108.     bt->left = binary_tree_from_string(string, begin + 1, closing_index - 1);
  109.     bt->right = binary_tree_from_string(string, closing_index + 2, end - 1);
  110.  
  111.     return bt;
  112. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement