#include <iostream>
#include <string>

// ===== Stack =====
template <typename T>
class Stack {
private:
    struct Node {
        T data;
        Node* next;
        Node(const T& value, Node* nextNode = nullptr)
            : data(value), next(nextNode) {
        }
    };

    Node* topNode;

public:
    Stack() : topNode(nullptr) {}

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

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

    void pop() {
        if (isEmpty()) {
            std::cerr << "Error: Stack is empty, cannot pop.\n";
            return;
        }
        Node* temp = topNode;
        topNode = topNode->next;
        delete temp;
    }

    T& top() {
        if (isEmpty()) {
            std::cerr << "Error: Stack is empty.\n";
            std::exit(1);
        }
        return topNode->data;
    }

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

// ===== Utils =====
bool isNumber(const std::string& s) {
    if (s.empty()) return false;
    size_t start = 0;
    if (s[0] == '-' && s.size() > 1) start = 1;
    for (size_t i = start; i < s.size(); ++i)
        if (s[i] < '0' || s[i] > '9') return false;
    return true;
}

int toInt(const std::string& s) {
    int result = 0;
    bool negative = false;
    size_t i = 0;
    if (s[0] == '-') { negative = true; i = 1; }
    for (; i < s.size(); ++i) result = result * 10 + (s[i] - '0');
    return negative ? -result : result;
}

// ===== RPN Evaluation =====
int evaluateRPN(const std::string& input) {
    Stack<int> stack;
    std::string token = "";

    for (size_t i = 0; i <= input.length(); ++i) {
        char ch = (i < input.length()) ? input[i] : ' ';

        if (ch != ' ') {
            token += ch;
        }
        else if (!token.empty()) {
            if (isNumber(token)) {
                stack.push(toInt(token));
            }
            else if (token == "+" || token == "-" || token == "*" || token == "/") {
                if (stack.isEmpty()) return -999999; // Error code
                int b = stack.top(); stack.pop();
                if (stack.isEmpty()) return -999999;
                int a = stack.top(); stack.pop();

                if (token == "+") stack.push(a + b);
                else if (token == "-") stack.push(a - b);
                else if (token == "*") stack.push(a * b);
                else if (token == "/") {
                    if (b == 0) return -888888; // Деление на 0
                    stack.push(a / b);
                }
            }
            else {
                std::cerr << "Unknown token: " << token << "\n";
                return -777777; // Некорректный токен
            }
            token = "";
        }
    }

    if (!stack.isEmpty()) {
        int result = stack.top(); stack.pop();
        if (!stack.isEmpty()) return -666666; // Stack not empty at end — ошибка
        return result;
    }

    return -555555; // Пустой ввод
}

// ===== Stack Test =====
void testStack() {
    std::cout << "[Stack Test]\n";
    Stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);

    if (s.top() == 3) std::cout << "Top OK\n";
    else std::cout << "Top FAIL\n";

    s.pop();
    if (s.top() == 2) std::cout << "Pop OK\n";
    else std::cout << "Pop FAIL\n";

    s.pop(); s.pop();
    if (s.isEmpty()) std::cout << "Empty OK\n";
    else std::cout << "Empty FAIL\n";

    std::cout << "\n";
}

// ===== RPN Test =====
void testRPN() {
    std::cout << "[RPN Test]\n";

    struct TestCase {
        std::string expr;
        int expected;
    };

    TestCase cases[] = {
        {"3 4 +", 7},
        {"10 2 * 3 +", 23},
        {"15 7 1 1 + - / 3 * 2 1 1 + + -", 5},
        {"5 1 2 + 4 * + 3 -", 14},
        {"3 0 /", -888888},  // деление на 0
        {"5 +", -999999},    // недостаточно операндов
        {"1 2 3 +", -666666} // лишнее на стеке
    };

    for (int i = 0; i < sizeof(cases) / sizeof(TestCase); ++i) {
        int result = evaluateRPN(cases[i].expr);
        std::cout << "Test " << i + 1 << ": ";
        if (result == cases[i].expected)
            std::cout << "OK";
        else
            std::cout << "FAIL (got " << result << ", expected " << cases[i].expected << ")";
        std::cout << "\n";
    }

    std::cout << "\n";
}

// ===== Main =====
int main() {
    testStack();
    testRPN();

    std::string input;
    std::cout << "Enter RPN expression (e.g. '3 4 + 2 *'): ";
    std::getline(std::cin, input);

    int result = evaluateRPN(input);
    std::cout << "Result: " << result << "\n";

    return 0;
}