//chatgpt

#include <iostream>
#include <string>

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;
    }
};

// Простейшая проверка: является ли строка числом (включая отрицательные)
bool isNumber(const std::string& s) {
    if (s.empty()) return false;
    size_t start = 0;
    if (s[0] == '-') {
        if (s.size() == 1) return false;
        start = 1;
    }
    for (size_t i = start; i < s.size(); ++i) {
        if (s[i] < '0' || s[i] > '9') return false;
    }
    return true;
}

// Простейший stoi, без std::stoi
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;
}

void 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()) { std::cerr << "Not enough operands\n"; return; }
                int b = stack.top(); stack.pop();

                if (stack.isEmpty()) { std::cerr << "Not enough operands\n"; return; }
                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 == "/") stack.push(a / b); // Без проверки деления на 0 для простоты
            } else {
                std::cerr << "Unknown token: " << token << "\n";
                return;
            }
            token = "";
        }
    }

    if (!stack.isEmpty()) {
        std::cout << "Result: " << stack.top() << "\n";
    } else {
        std::cerr << "No result on stack\n";
    }
}

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

    evaluateRPN(input);

    return 0;
}