lab2

#include <iostream>
#include <string>
#include <stack>

using namespace std;

// Функция, которая определяет приоритет операторов
int priority(char c) {
    if (c == '(') {
        return 0;
    }
    if (c == '+' || c == '-') {
        return 1;
    }
    if (c == '*' || c == '/') {
        return 2;
    }
    return 3;
}

// Функция, которая проверяет, является ли символ оператором
bool isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/');
}

// Функция, которая проверяет, является ли выражение корректным
bool isExpressionValid(string infix) {
    stack<char> parentheses;
    bool previousWasOperator = false;

    for (int i = 0; i < infix.length(); i++) {
        char c = infix[i];
        if (c == '(') {
            parentheses.push(c);
            previousWasOperator = false;
        } else if (c == ')') {
            if (parentheses.empty() || parentheses.top() != '(' || previousWasOperator) {
                return false; // Несоответствие скобок или оператор после скобки
            }
            parentheses.pop();
            previousWasOperator = false;
        } else if (isOperator(c)) {
            if (previousWasOperator) {
                return false; // Два оператора подряд
            }
            previousWasOperator = true;
        } else if (isdigit(c)) {
            previousWasOperator = false;
        } else if (c != ' ') {
            return false; // Недопустимый символ
        }
    }

    return parentheses.empty() && !previousWasOperator; // Все скобки сбалансированы и выражение заканчивается операндом
}

// Функция, которая преобразует инфиксное выражение в постфиксное
string infixToPostfix(string infix) {
    if (!isExpressionValid(infix)) {
        return "Invalid expression";
    }

    stack<char> operators;
    string postfix;
    int postfixSize = 0;
    int infixSize = infix.length();

    // Динамическое выделение памяти для хранения постфиксного выражения
    char* postfixArray = new char[infixSize];

    for (int i = 0; i < infixSize; i++) {
        char c = infix[i];

        if (c == ' ') {
            continue;
        }

        if (isdigit(c)) {
            postfixArray[postfixSize++] = c;
        } else if (c == '(') {
            operators.push(c);
        } else if (c == ')') {
            while (!operators.empty() && operators.top() != '(') {
                postfixArray[postfixSize++] = operators.top();
                operators.pop();
            }
            if (!operators.empty() && operators.top() == '(') {
                operators.pop();
            }
        } else if (isOperator(c)) {
            while (!operators.empty() && priority(c) <= priority(operators.top())) {
                postfixArray[postfixSize++] = operators.top();
                operators.pop();
            }
            operators.push(c);
        }
    }

    while (!operators.empty()) {
        postfixArray[postfixSize++] = operators.top();
        operators.pop();
    }

    // Преобразование динамического массива в строку
    postfix = string(postfixArray, postfixSize);

    delete[] postfixArray; // Освобождение выделенной памяти

    return postfix;
}

// Тесты
int main() {
    cout << infixToPostfix("2 + 3") << endl; // ожидаемый результат: "23+"
    cout << infixToPostfix("2 * (3 + 4)") << endl; // ожидаемый результат: "234+*"
    cout << infixToPostfix("2 + 3 * 4") << endl; // ожидаемый результат: "234*+"

    // Некорректные выражения
    cout << infixToPostfix("2 + (3 * 4") << endl; // ожидаемый результат: "Invalid expression" (несоответствие скобок)
    cout << infixToPostfix("2 + * 3") << endl; // ожидаемый результат: "Invalid expression" (ошибка в выражении)

    return 0;
}