Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- typedef struct node {
- int item;
- struct node *next;
- } node;
- typedef struct stack {
- node *top;
- } stack;
- typedef struct binary_tree {
- int item;
- struct binary_tree *left;
- struct binary_tree *right;
- } binary_tree;
- // STACK
- stack *create_stack()
- {
- stack *new_stack = (stack*) malloc(sizeof(stack));
- new_stack->top = NULL;
- return new_stack;
- }
- node* create_node(int item)
- {
- node *new_node = (node*) malloc(sizeof(node));
- new_node->item = item;
- new_node->next = NULL;
- return new_node;
- }
- void push(stack *stack, int item)
- {
- node *new_node = create_node(item);
- new_node->next = stack->top;
- stack->top = new_node;
- }
- int is_empty(stack *stack)
- {
- return stack->top == NULL;
- }
- void pop(stack *stack)
- {
- if (is_empty(stack)) {
- printf("Stack underflow\n");
- } else {
- node *top = stack->top;
- stack->top = top->next;
- free(top);
- }
- }
- // BINARY TREE
- binary_tree* create_binary_tree(int item, binary_tree *left, binary_tree *right)
- {
- binary_tree *new_binary_tree = (binary_tree*) malloc(sizeof(binary_tree));
- new_binary_tree->item = item;
- new_binary_tree->left = left;
- new_binary_tree->right = right;
- return new_binary_tree;
- }
- int closing_bracket_index(char *string, int begin, int end)
- {
- stack *stack = create_stack();
- while (begin <= end) {
- if (string[begin] == '(') {
- push(stack, 1);
- } else if (string[begin] == ')') {
- pop(stack);
- if (is_empty(stack)) {
- free(stack);
- return begin;
- }
- }
- begin++;
- }
- return -1;
- }
- binary_tree* binary_tree_from_string(char *string, int begin, int end)
- {
- if (begin >= end) return NULL;
- char number[11];
- int len = 0;
- while (string[begin] >= 48 && string[begin] <= 57) {
- number[len++] = string[begin];
- begin++;
- }
- number[len] = '\0';
- if (strlen(number) == 0) return NULL;
- int value = atoi(number);
- binary_tree *bt = create_binary_tree(value, NULL, NULL);
- int closing_index = closing_bracket_index(string, begin, end);
- bt->left = binary_tree_from_string(string, begin + 1, closing_index - 1);
- bt->right = binary_tree_from_string(string, closing_index + 2, end - 1);
- return bt;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement