Как удалить лишние скобки, используя обратную польскую нотацию?

Исходное выражение ((a * b) + (6 + (4))) * c.

Польская нотация a b * 6 4 + + c *.

Для обратного перевода из польской нотации нужен стек. В стеке хранятся пары '<строка>':<приоритет>. Токены польской нотации обрабатываются слева направо. Стек обновляется соответственно: если токен - число, оно помещается в стек, если операция, то она снимает со стека свои аргументы-подвыражения, объединяет их в новую строку-выражение, которую помещает на стек со своим приоритетом. Приоритеты токенов для польской нотации выбираются из таблицы. Например: число -> 1, сложение -> 2, умножение -> 3:

токен   стек
        []
a:3     ['a':3]
b:3     ['a':3, 'b':3]
*:2     ['a * b':2]
6:3     ['a * b':2, '6':3]
4:3     ['a * b':2, '6':3, '4':3]
+:1     ['a * b':2, '6 + 4':1]
+:1     ['a * b + 6 + 4':1]
c:3     ['a * b + 6 + 4':1, 'c':3]
*:2     ['(a * b + 6 + 4) * c':3]

Обратите внимание на последнюю строку. Первое подвыражение (a * b + 6 + 4) выделено скобками потому что имеет приоритет (1) ниже чем операция умножение (2). Второе подвыражение (c) имеет приоритет (3) выше и в скобках не нуждается.

Прошу не сильно судить мой ответ, я просто делюсь своим кодом и опытом:

Сложение, вычитание, умножение огромных чисел на С (код нуждается в оптимизации, но он рабочий). Если у вас выполнение программы останавливается по непонятным причинам, то это связанно со стеком и компилятором (gcc). После сборки на cmake все заработало отлично, возможно у вас такого не случится и это моя локальная проблема

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <ctype.h>
// #include <windows.h>
#include <locale.h>
#include <stdint.h>
#include <inttypes.h>


#define MAX_DIGITS 100000
#define MAX_LENGTH 100000

// Структура для узла связного списка, представляющего операнд или операцию
typedef struct Node {
    char* data;
    struct Node* next;
} Node;

// Стек для операндов и промежуточных результатов
typedef struct Stack {
    Node* top;
} Stack;

// Инициализация стека
Stack* initStack() {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    if (stack == NULL) {
        printf("Memory allocation failed\n");
        exit(5);
    }
    stack->top = NULL;
    return stack;
}

// Проверка на пустоту стека
bool isEmpty(Stack* stack) {
    return stack->top == NULL;
}

// Добавление элемента на вершину стека
void push(Stack* stack, char* data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(5);
    }
    newNode->data = strdup(data);
    newNode->next = stack->top;
    stack->top = newNode;
}

// Ну че FILO, поцаны?)
char* pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        exit(5);
    }
    Node* topNode = stack->top;
    char* data = strdup(topNode->data);
    stack->top = topNode->next;
    free(topNode->data);
    free(topNode);
    return data;
}

// Очистка памяти, выделенной для стека
void freeStack(Stack* stack) {
    while (!isEmpty(stack)) {
        pop(stack);
    }
    free(stack);
}

void reverseString(char* str) {
    int length = strlen(str);
    int i, j;

    for (i = 0, j = length - 1; i < j; ++i, --j) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }
}

void removeTrailingZeros(char* str) {
    int length = strlen(str);
    int i;

    // Находим индекс первого числа, не равного нулю
    for (i = length - 1; i >= 0; --i) {
        if (str[i] != '0') {
            break;
        }
    }

    // Сдвигаем данные влево, удаляя хвостовые нули
    memmove(str, str, i + 1);
    str[i + 1] = '\0'; // Добавляем нулевой символ в конец строки
}

int compareStrings(const char *str1, const char *str2) {
    int len1 = strlen(str1);
    int len2 = strlen(str2);

    if (len1 > len2) {
        return 1; // Если длина str1 больше длины str2
    } else if (len1 < len2) {
        return -1; // Если длина str1 меньше длины str2
    } else {
        int i = 0;
        while (i < len1) {
            if (str1[i] > str2[i]) {
                return 1; // Если символ в str1 больше символа в str2
            } else if (str1[i] < str2[i]) {
                return -1; // Если символ в str1 меньше символа в str2
            }
            i++;
        }
        return 0; // Если строки равны
    }
}

char* process_first_character(const char* str) {
    int len = strlen(str);

    // Выделяем память под новую строку, размер которой на единицу меньше исходной строки
    char* result = (char*)malloc(len);
    if (result == NULL) {
        printf("Ошибка выделения памяти.\n");
        exit(5);
    }

    // Если первый символ в строке равен '-' (минусу)
    if (str[0] == '-') {
        // Копируем строку, начиная со второго символа
        strcpy(result, str + 1);
    } else {
        // Если первый символ не минус, то добавляем его в начало строки
        result[0] = '-';
        // Копируем остальную часть строки
        strcpy(result + 1, str);
    }

    return result;
}

// Мы используем разные функции для чисел с одинаковым знаком и разным
char* add_long_numbers_same_sign(const char* num1, const char* num2) {

    int len1 = strlen(num1);
    int len2 = strlen(num2);

    char sign1 = num1[0];
    char sign2 = num2[0];

    // Determine the sign of the result
    int sign = 1;
    if (num1[0] == '-') {
        sign *= -1;
        num1++;
        len1--;
    }
    if (num2[0] == '-') {
        sign *= -1;
        num2++;
        len2--;
    }

    // Allocate memory for the sum
    int maxSize = len1 > len2 ? len1 : len2;
    int* sum = (int*)calloc(maxSize + 1, sizeof(int));

    int carry = 0;
    int k = maxSize;
    int i = len1 - 1, j = len2 - 1;

    while (i >= 0 || j >= 0) {
        int digit1 = i >= 0 ? num1[i--] - '0' : 0;
        int digit2 = j >= 0 ? num2[j--] - '0' : 0;
        int total = digit1 + digit2 + carry;
        sum[k--] = total % 10;
        carry = total / 10;
    }

    if (carry > 0) {
        sum[k] += carry;
    }

    // Convert the sum to a string
    int start = (sum[k] == 0) ? k + 1 : k;
    int resultSize = maxSize - start + 2;
    char* result = (char*)malloc(resultSize * sizeof(char));
    
    for (int idx = start, r = 0; idx <= maxSize; idx++, r++) {
        result[r] = sum[idx] + '0';
    }
    result[resultSize - 1] = '\0';

    // Consider the sign of the result

    if (sign1 == '-' && sign2 == '-') {
        sign = -1;
    }

    if (sign == -1) {
        char* signedResult = (char*)malloc((resultSize + 1) * sizeof(char));
        signedResult[0] = '-';
        strcpy(signedResult + 1, result);
        free(result);
        free(sum);
        return signedResult;
    } else {
        free(sum);
        return result;
    }
}

char* add_long_numbers_different_sign(const char* num1, const char* num2) {

    char sign1 = num1[0];
    char sign2 = num2[0];

    const char* abs_num1 = (sign1 == '-' || sign1 == '+') ? num1 + 1 : num1;
    const char* abs_num2 = (sign2 == '-' || sign2 == '+') ? num2 + 1 : num2;

    int abs_len1 = strlen(abs_num1);
    int abs_len2 = strlen(abs_num2);

    int result_len = (abs_len1 > abs_len2 ? abs_len1 : abs_len2) + 1;

    char* result = (char*)malloc((result_len + 1) * sizeof(char));

    if (result == NULL) {
        printf("Memory allocation failed\n");
        exit(5);
    }

    result[0] = '\0';

    int carry = 0;
    int i = abs_len1 - 1;
    int j = abs_len2 - 1;
    int k = result_len - 1;
    int abs_result_len = (abs_len1 > abs_len2 ? abs_len1 : abs_len2);

    while (i >= 0 || j >= 0 || carry > 0) {
        int digit1 = (i >= 0) ? abs_num1[i] - '0' : 0;
        int digit2 = (j >= 0) ? abs_num2[j] - '0' : 0;
        

        int difference = digit1 - digit2 - carry; 

        // Если разница меньше 0, добавляем 10 и устанавливаем перенос
        if (difference < 0 && strlen(result) <= result_len) {
            difference += 10;
            carry = 1;
        } else {
            carry = 0;
        }
        k--;
        sprintf(result + strlen(result), "%d", difference);



        if (i >= 0) i--;
        if (j >= 0) j--;
    }

    abs_result_len = strlen(result);


    removeTrailingZeros(result);

    reverseString(result); // Переворачиваем строку

    return result;
}

char* add_long_numbers(const char* num1, const char* num2) {

    char* result;
    
    if((num1[0] == '-' && num2[0] == '-') || (isdigit(num1[0]) && isdigit(num2[0]))) {
        result = add_long_numbers_same_sign( num1, num2);
    } else {

        char sign1 = num1[0];
        char sign2 = num2[0];


        const char* abs_num1 = (sign1 == '-' || sign1 == '+') ? num1 + 1 : num1;
        const char* abs_num2 = (sign2 == '-' || sign2 == '+') ? num2 + 1 : num2;

    
        int abs_len1 = strlen(abs_num1);
        int abs_len2 = strlen(abs_num2);


        if(compareStrings(abs_num1, abs_num2) == 1) {
            if(sign1 == '-') {
                result = add_long_numbers_different_sign( process_first_character(num1), process_first_character(num2));
                result = process_first_character(result);
            } else {
                result = add_long_numbers_different_sign( (num1), (num2));
            }
        } else {
            if(sign2 == '-') {
                result = add_long_numbers_different_sign( process_first_character(num2), process_first_character(num1));
                result = process_first_character(result);
            } else {
                result = add_long_numbers_different_sign( num2, num1);
            }
        }

    }
    

    return result;
}

// Вычитание
char* subtract_long_numbers(const char* num1, char* num2) {

    return add_long_numbers(num1, process_first_character(num2));
}

// Функция для умножения длинных чисел
char* multiply_long_numbers(char *num1, char *num2) {

    int len1 = strlen(num1);
    int len2 = strlen(num2);

    // Определяем знак результата
    int sign = 1;
    if (num1[0] == '-') {
        sign *= -1;
        num1++;
        len1--;
    }
    if (num2[0] == '-') {
        sign *= -1;
        num2++;
        len2--;
    }

    // Результат умножения не превысит сумму длин входных чисел
    int *prod = (int*)calloc(len1 + len2, sizeof(int));

    // Перемножаем цифры и складываем результаты
    for (int i = len1 - 1; i >= 0; i--) {
        for (int j = len2 - 1; j >= 0; j--) {
            int digit1 = num1[i] - '0';
            int digit2 = num2[j] - '0';
            int sum = digit1 * digit2 + prod[i + j + 1];
            prod[i + j + 1] = sum % 10;
            prod[i + j] += sum / 10;
        }
    }

    // Преобразуем результат в строку
    int k = 0;
    while (k < len1 + len2 && prod[k] == 0) {
        k++;
    }

    if (k == len1 + len2) {
        char *result = (char*)malloc(2 * sizeof(char));
        strcpy(result, "0");
        free(prod);
        return result;
    }

    char *result = (char*)malloc((len1 + len2 - k + 1) * sizeof(char));
    for (int i = k; i < len1 + len2; i++) {
        result[i - k] = prod[i] + '0';
    }
    result[len1 + len2 - k] = '\0';

    // Учитываем знак результата
    if (sign == -1) {
        char *signedResult = (char*)malloc((len1 + len2 - k + 2) * sizeof(char));
        signedResult[0] = '-';
        strcpy(signedResult + 1, result);
        free(result);
        return signedResult;
    } else {
        return result;
    }
}

// Функция для вычисления выражения в обратной польской нотации
char* evaluateRPN(char* expression[]) {
    Stack* stack = initStack();

    // Перебираем каждый элемент выражения
    for (int i = 0; expression[i] != NULL; i++) {

        // Если элемент - число, помещаем его в стек
        if (isdigit(expression[i][0]) || (expression[i][0] == '-' && isdigit(expression[i][1]))) {
            push(stack, expression[i]);
        } else {
            // Если элемент - оператор, извлекаем два последних числа из стека,
            // выполняем операцию и помещаем результат обратно в стек
            char* operand2_str = pop(stack);
            char* operand1_str = pop(stack);


            char* result;
            switch (expression[i][0]) {
                case '+':
                    result = add_long_numbers(operand1_str, operand2_str);
                    break;
                case '-':
                    result = subtract_long_numbers(operand1_str, operand2_str);
                    break;
                case '*':
                    result = multiply_long_numbers(operand1_str, operand2_str);
                    break;
                case '/':
                    result = multiply_long_numbers(operand1_str, operand2_str);\
                    printf("Операция деления не поддерживается\n");
                    exit(3);
                default:
                    printf("Invalid operator\n");
                    exit(4);
            }
            
            push(stack, result);        

            // Очистка памяти, выделенной для операндов
            free(operand1_str);
            free(operand2_str);
            // free(result);
        }
    }

    // Результат на вершине стека
    char* result = strdup(pop(stack));

    // Очищаем стек и возвращаем результат
    freeStack(stack);
    return result;
}

int main(int argc, char *argv[]) {

    //  SetConsoleOutputCP(CP_UTF8); // Установка кодовой страницы для вывода русского текста в консоль на Windows
    setlocale(LC_ALL, "Russian");

    if (strcmp(argv[1], "--infix") == 0) {
        fprintf(stderr, "Ошибка: данная версия программы не поддерживает инфиксную нотацию\n");
        exit(2);
    }

    if (argc < 2 || strcmp(argv[1], "--revpol") != 0) {
        fprintf(stderr, "Usage: %s --revpol <expression>\n", argv[0]);
        exit(1);
    }

    char* tokens[10000]; // Массив указателей на подстроки
    int num_tokens = 0;

    // Используем strtok для разбиения строки на подстроки
    char* expression = strtok(argv[2], " ");
    while (expression != NULL) {
        tokens[num_tokens++] = expression;
        expression = strtok(NULL, " ");
    }

    // Вычисляем результат выражения
    char* result = evaluateRPN(tokens);
    
    printf("Result: %s\n", result); // Ожидаемый результат: 61

    // Очищаем память, выделенную для результата
    free(result);

    return EXIT_SUCCESS;
}

Для запуска используйте --revpol "выражение в двойных кавычках"