Answered: (10 3 3 (18 ( 10 + ( 8 / 3 ) ) + ( 5 *…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

Write a function that gets a binary tree representing an arithmetic expression and returns a string containing the expression. For operations we use the following enum.

enum {PLUS = '+', MINUS = '-', MULT = '*', DIV = '/'};

// converts a arithmetic expression from tree to string

char* get_arithmetic_expression(const BTnode_t* expression)

The expression must have parentheses for each operation (except for the outermost parentheses), and all tokens (numbers and operations) must be separated by a single space. See more examples for the exact format in the test file.

** Negative values are allowed,

** You may assume that all numbers are at most 3 digits long (incl. minus sign)

** YOu may assume the expression is alway legal

** You may find the function sprintf() useful here. The function is similar to printf(), but prints to string, e.g, sprintf(str, “%d”, 15); prints 15 to str.

struct representing node in the binary tree:

struct BTnode {

int value;

struct BTnode* left;

struct BTnode* right;

struct BTnode* parent;

};

typedef struct BTnode BTnode_t;

test for the function:

bool test_q2() {

/***

// creates the following tree

// +

// / \

// * +

// / \ / \

// 3 - 5 /

// / \ / \

// 9 7 8 -2

****/

BTnode_t* root_plus = create_node(PLUS);

BTnode_t* mult = create_node(MULT);

BTnode_t* plus = create_node(PLUS);

BTnode_t* minus = create_node(MINUS);

BTnode_t* div = create_node(DIV);

BTnode_t* neg_two = create_node(-2);

BTnode_t* three = create_node(3);

BTnode_t* five = create_node(5);

BTnode_t* seven = create_node(7);

BTnode_t* eight = create_node(8);

BTnode_t* nine = create_node(9);

set_left_child(root_plus, mult);

set_right_child(root_plus, plus);

set_left_child(mult, three);

set_right_child(mult, minus);

set_left_child(plus, five);

set_right_child(plus, div);

set_left_child(minus, nine);

set_right_child(minus, seven);

set_left_child(div, eight);

set_right_child(div, neg_two);

char* ans8 = get_arithmetic_expression(eight);

boolcheck8 = (ans8 && strcmp(ans8, "8") == 0);

if (check8)

printf("Q2: 8 ok\n");

else

printf("Q2: 8 ERROR: %s\n", ans8);

char* ans_neg_two = get_arithmetic_expression(neg_two);

boolcheck_neg_two = (ans_neg_two && strcmp(ans_neg_two, "-2") == 0);

if (check_neg_two)

printf("Q2: -2 ok\n");

else

printf("Q2: -2 ERROR: %s\n", ans_neg_two);

char* ans_minus = get_arithmetic_expression(minus);

boolcheck_minus = (ans_minus && strcmp(ans_minus, "9 - 7") == 0);

if (check_minus)

printf("Q2: 9-7 ok\n");

else

printf("Q2: 9-7 ERROR: %s\n", ans_minus);

char* ans_mult = get_arithmetic_expression(mult);

boolcheck_mult = (ans_mult && strcmp(ans_mult, "3 * ( 9 - 7 )") == 0);

if (check_mult)

printf("Q2: 3*(9-7) ok\n");

else

printf("Q2: 3*(9-7) ERROR: %s\n", ans_mult);

charcorrect_ans[] = "( 3 * ( 9 - 7 ) ) + ( 5 + ( 8 / -2 ) )";

char* ans_root = get_arithmetic_expression(root_plus);

boolcheck_rook = (ans_root && strcmp(ans_root, correct_ans) == 0);

if (check_rook)

printf("Q2: root ok\n");

else

printf("Q2: root ERROR: %s\n", ans_root);

return true;

}

Library for the function:

BTnode_t* create_node(int val) {

BTnode_t* newNode = (BTnode_t*) malloc(sizeof(BTnode_t));

newNode->value = val;

newNode->left = NULL;

newNode->right = NULL;

newNode->parent = NULL;

returnnewNode;

}

void set_left_child(BTnode_t* parent, BTnode_t* left_child) {

if (parent)

parent->left = left_child;

if (left_child)

left_child->parent = parent;

}

void set_right_child(BTnode_t* parent, BTnode_t* right_child) {

if (parent)

parent->right = right_child;

if (right_child)

right_child->parent = parent;

}

void print_pre_order(BTnode_t* root) {

if (root == NULL)

return;

printf("%d ", root->value);

print_pre_order(root->left);

print_pre_order(root->right);

}

void print_in_order(BTnode_t* root) {

if (root == NULL)

return;

print_in_order(root->left);

printf("%d ", root->value);

print_in_order(root->right);

}

void print_post_order(BTnode_t* root) {

if (root == NULL)

return;

print_post_order(root->left);

print_post_order(root->right);

printf("%d ", root->value);

}

6
8
3
(10
8
3
5
(18
( 10 + ( 8 / 3 )) + ( 5 * ( 5 - 18 ) )
6 + 3
8
+

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions