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

// Структура для представления узла дерева
typedef struct Node {
    char data;
    struct Node* left;
    struct Node* right;
} Node;

// Функция для создания нового узла
Node* createNode(char data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Функция для освобождения памяти, выделенной под дерево
void freeTree(Node* root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

// Функция для преобразования выражения в дерево
Node* expressionToTree(const char* expression, int* index) {
    char token = expression[*index];

    if (token == '(') {
        (*index)++; // Пропускаем '('
        token = expression[*index];

        Node* root = createNode(token);
        (*index)++; // Переходим к следующему токену

        root->left = expressionToTree(expression, index);

        (*index)++; // Пропускаем символ операции
        token = expression[*index];

        root->right = expressionToTree(expression, index);

        (*index)++; // Пропускаем ')'
        return root;
    } else {
        return createNode(token);
    }
}

// Функция для обхода дерева и выполнения преобразований
Node* transformExpression(Node* root) {
    if (root == NULL) {
        return NULL;
    }

    // Рекурсивно обрабатываем левое и правое поддеревья
    root->left = transformExpression(root->left);
    root->right = transformExpression(root->right);

    // Если текущий узел представляет операцию умножения
    if (root->data == '*') {
        // Выполняем преобразование (a*c)/(b*d)
        root->data = '/';
        Node* temp = createNode('*');
        temp->left = root->left->right;
        temp->right = root->right->left;
        root->left->right = temp;
        root->right->left = NULL;
    }

    return root;
}

// Функция для вывода выражения в виде инфиксной записи
void printInfix(Node* root) {
    if (root != NULL) {
        printf("(");
        printInfix(root->left);
        printf("%c", root->data);
        printInfix(root->right);
        printf(")");
    }
}

int main() {
    while (1) {
        // Ввод выражения с консоли
        printf("Enter an expression (or 'exit' to quit): ");
        char expression[100];
        fgets(expression, sizeof(expression), stdin);

        // Проверка на выход
        if (strcmp(expression, "exit\n") == 0) {
            break;
        }

        int index = 0;
        Node* root = expressionToTree(expression, &index);

        printf("Original Expression (Tree): ");
        printInfix(root);
        printf("\n");

        // Выполняем преобразование
        Node* result = transformExpression(root);

        printf("Transformed Expression (Tree): ");
        printInfix(result);
        printf("\n");

        // Освобождаем память, выделенную под дерево
        freeTree(root);
        freeTree(result);
    }

    return 0;
}