#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

bool isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/');
}

int getPrecedence(char op) {
    if (op == '+' || op == '-') {
        return 1;
    } else if (op == '*' || op == '/') {
        return 2;
    }
    return 0;
}

string infixToPrefix(string infix) {
    stack<char> operators;
    stack<string> operands;

    reverse(infix.begin(), infix.end());

    for (char& c : infix) {
        if (isalnum(c)) {
            operands.push(string(1, c));
        } else if (c == ')') {
            operators.push(c);
        } else if (c == '(') {
            while (!operators.empty() && operators.top() != ')') {
                string operand1 = operands.top();
                operands.pop();
                string operand2 = operands.top();
                operands.pop();
                char op = operators.top();
                operators.pop();
                operands.push(op + operand2 + operand1);
            }
            operators.pop();
        } else if (isOperator(c)) {
            while (!operators.empty() && getPrecedence(operators.top()) >= getPrecedence(c)) {
                string operand1 = operands.top();
                operands.pop();
                string operand2 = operands.top();
                operands.pop();
                char op = operators.top();
                operators.pop();
                operands.push(op + operand2 + operand1);
            }
            operators.push(c);
        }
    }

    while (!operators.empty()) {
        string operand1 = operands.top();
        operands.pop();
        string operand2 = operands.top();
        operands.pop();
        char op = operators.top();
        operators.pop();
        operands.push(op + operand2 + operand1);
    }

    return operands.top();
}

int evaluatePrefix(string prefix) {
    stack<int> s;

    reverse(prefix.begin(), prefix.end());

    for (char& c : prefix) {
        if (isdigit(c)) {
            s.push(c - '0');
        } else {
            int operand1 = s.top();
            s.pop();
            int operand2 = s.top();
            s.pop();

            switch (c) {
                case '+':
                    s.push(operand1 + operand2);
                    break;
                case '-':
                    s.push(operand1 - operand2);
                    break;
                case '*':
                    s.push(operand1 * operand2);
                    break;
                case '/':
                    s.push(operand1 / operand2);
                    break;
            }
        }
    }

    return s.top();
}

int main() {
    string infixExpression;
    cout << "Enter infix expression: ";
    cin >> infixExpression;

    string prefixExpression = infixToPrefix(infixExpression);
    cout << "Prefix expression: " << prefixExpression << endl;

    int result = evaluatePrefix(prefixExpression);
    cout << "Result: " << result << endl;

    return 0;
}