//// deepseek
#include <iostream>

// Шаблонный класс Stack
template <typename T>
class Stack {
private:
    struct Node {
        T data;
        Node* next;
        Node(const T& data, Node* next = nullptr) : data(data), next(next) {}
    };

    Node* topNode;
    size_t stackSize;

public:
    Stack() : topNode(nullptr), stackSize(0) {}

    ~Stack() {
        while (!empty()) {
            pop();
        }
    }

    void push(const T& value) {
        Node* newNode = new Node(value, topNode);
        topNode = newNode;
        stackSize++;
    }

    void pop() {
        if (empty()) {
            std::cerr << "Error: Stack is empty, cannot pop\n";
            return;
        }

        Node* temp = topNode;
        topNode = topNode->next;
        delete temp;
        stackSize--;
    }

    T& top() {
        if (empty()) {
            std::cerr << "Error: Stack is empty, returning garbage value\n";
            static T garbage;
            return garbage;
        }
        return topNode->data;
    }

    const T& top() const {
        if (empty()) {
            std::cerr << "Error: Stack is empty, returning garbage value\n";
            static T garbage;
            return garbage;
        }
        return topNode->data;
    }

    bool empty() const {
        return topNode == nullptr;
    }

    size_t size() const {
        return stackSize;
    }
};

// Вспомогательные функции для калькулятора
bool isDigit(char c) {
    return c >= '0' && c <= '9';
}

double parseNumber(const char*& str) {
    double num = 0;
    bool negative = false;
    bool decimal = false;
    double decimalDivisor = 1.0;

    if (*str == '-') {
        negative = true;
        ++str;
    }

    while (isDigit(*str) || *str == '.') {
        if (*str == '.') {
            decimal = true;
            ++str;
            continue;
        }

        if (decimal) {
            decimalDivisor *= 10;
            num += (*str - '0') / decimalDivisor;
        }
        else {
            num = num * 10 + (*str - '0');
        }
        ++str;
    }

    return negative ? -num : num;
}

// Функция вычисления выражения в ОПН
double evaluateRPN(const char* expression) {
    Stack<double> stack;

    while (*expression != '\0') {
        // Пропускаем пробелы
        if (*expression == ' ') {
            ++expression;
            continue;
        }

        // Если цифра или минус (начало числа)
        if (isDigit(*expression) || (*expression == '-' && isDigit(*(expression + 1)))) {
            stack.push(parseNumber(expression));
        }
        else {
            // Операция
            if (stack.size() < 2) {
                std::cerr << "Error: Not enough operands for operation\n";
                return 0;
            }

            double b = stack.top(); stack.pop();
            double a = stack.top(); stack.pop();

            switch (*expression) {
            case '+': stack.push(a + b); break;
            case '-': stack.push(a - b); break;
            case '*': stack.push(a * b); break;
            case '/':
                if (b == 0) {
                    std::cerr << "Error: Division by zero\n";
                    return 0;
                }
                stack.push(a / b);
                break;
            default:
                std::cerr << "Error: Unknown operator '" << *expression << "'\n";
                return 0;
            }
            ++expression;
        }
    }

    if (stack.size() != 1) {
        std::cerr << "Error: Invalid expression format\n";
        return 0;
    }

    return stack.top();
}

// Тестирование стека
void testStack() {
    std::cout << "=== Testing Stack ===\n";
    Stack<int> s;

    s.push(1);
    s.push(2);
    s.push(3);

    std::cout << "Top: " << s.top() << " (expected 3)\n";
    s.pop();
    std::cout << "Top after pop: " << s.top() << " (expected 2)\n";
    std::cout << "Size: " << s.size() << " (expected 2)\n";
    std::cout << "Empty: " << (s.empty() ? "true" : "false") << " (expected false)\n";

    s.pop();
    s.pop();
    std::cout << "Empty after pops: " << (s.empty() ? "true" : "false") << " (expected true)\n";

    // Тест на пустом стеке
    s.top(); // Должно вывести ошибку
    s.pop(); // Должно вывести ошибку
}

// Тестирование калькулятора
void testCalculator() {
    std::cout << "\n=== Testing RPN Calculator ===\n";

    const char* test1 = "3 4 +"; // 3 + 4 = 7
    const char* test2 = "5 1 2 + 4 * +"; // 5 + (1 + 2) * 4 = 17
    const char* test3 = "10 6 - 2 /"; // (10 - 6) / 2 = 2
    const char* test4 = "3.5 2 *"; // 3.5 * 2 = 7
    const char* test5 = "-5 3 +"; // -5 + 3 = -2

    std::cout << test1 << " = " << evaluateRPN(test1) << " (expected 7)\n";
    std::cout << test2 << " = " << evaluateRPN(test2) << " (expected 17)\n";
    std::cout << test3 << " = " << evaluateRPN(test3) << " (expected 2)\n";
    std::cout << test4 << " = " << evaluateRPN(test4) << " (expected 7)\n";
    std::cout << test5 << " = " << evaluateRPN(test5) << " (expected -2)\n";

    // Тест ошибок
    std::cout << "\nTesting errors:\n";
    evaluateRPN("1 2 + +"); // Недостаточно операндов
    evaluateRPN("1 0 /");   // Деление на ноль
    evaluateRPN("1 2 &");   // Неизвестный оператор
}

int main() {
    testStack();
    testCalculator();

    // Интерактивный режим
    std::cout << "\n=== Interactive RPN Calculator ===\n";
    std::cout << "Enter expression (e.g. '3 4 + 2 *'), 'q' to quit\n";

    char input[256];
    while (true) {
        std::cout << "> ";
        std::cin.getline(input, sizeof(input));

        if (input[0] == 'q') break;

        double result = evaluateRPN(input);
        std::cout << "= " << result << "\n";
    }

    return 0;
}