#include <iostream>
#include <stack>
#include <string>
#include <sstream>
#include <cctype>
#include <vector>
#include <map>
 
using namespace std;
 
// Пріоритети операторів
map<char, int> precedence = {
    {'+', 1}, {'-', 1},
    {'*', 2}, {'/', 2},
    {'(', 0}  // Дужки мають найнижчий пріоритет
};
 
// Функція перевірки, чи символ є оператором
bool isOperator(char c) {
    return precedence.count(c) > 0;
}
 
// Перетворення інфіксного виразу в постфіксний
string infixToPostfix(const string& infix) {
    stack<char> operators;
    stringstream output;
 
    for (size_t i = 0; i < infix.length(); i++) {
        char token = infix[i];
 
        // Якщо символ — число або літера, додаємо його у вихідний рядок
        if (isalnum(token)) {
            output << token;
        }
        // Якщо символ — оператор
        else if (isOperator(token)) {
            while (!operators.empty() && precedence[operators.top()] >= precedence[token]) {
                output << ' ' << operators.top();
                operators.pop();
            }
            output << ' ';
            operators.push(token);
        }
        // Якщо символ — відкрита дужка, додаємо в стек
        else if (token == '(') {
            operators.push(token);
        }
        // Якщо символ — закрита дужка, обробляємо стек
        else if (token == ')') {
            while (!operators.empty() && operators.top() != '(') {
                output << ' ' << operators.top();
                operators.pop();
            }
            operators.pop(); // Видаляємо '('
        }
    }
 
    // Витягуємо залишки операторів зі стеку
    while (!operators.empty()) {
        output << ' ' << operators.top();
        operators.pop();
    }
 
    return output.str();
}
 
int main() {
    string infix = "3+4*2/(1-5)";
    cout << "Інфіксний запис: " << infix << endl;
    cout << "Постфіксний запис: " << infixToPostfix(infix) << endl;
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDxzc3RyZWFtPgojaW5jbHVkZSA8Y2N0eXBlPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8bWFwPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vINCf0YDRltC+0YDQuNGC0LXRgtC4INC+0L/QtdGA0LDRgtC+0YDRltCyCm1hcDxjaGFyLCBpbnQ+IHByZWNlZGVuY2UgPSB7CiAgICB7JysnLCAxfSwgeyctJywgMX0sCiAgICB7JyonLCAyfSwgeycvJywgMn0sCiAgICB7JygnLCAwfSAgLy8g0JTRg9C20LrQuCDQvNCw0Y7RgtGMINC90LDQudC90LjQttGH0LjQuSDQv9GA0ZbQvtGA0LjRgtC10YIKfTsKCi8vINCk0YPQvdC60YbRltGPINC/0LXRgNC10LLRltGA0LrQuCwg0YfQuCDRgdC40LzQstC+0Lsg0ZQg0L7Qv9C10YDQsNGC0L7RgNC+0LwKYm9vbCBpc09wZXJhdG9yKGNoYXIgYykgewogICAgcmV0dXJuIHByZWNlZGVuY2UuY291bnQoYykgPiAwOwp9CgovLyDQn9C10YDQtdGC0LLQvtGA0LXQvdC90Y8g0ZbQvdGE0ZbQutGB0L3QvtCz0L4g0LLQuNGA0LDQt9GDINCyINC/0L7RgdGC0YTRltC60YHQvdC40LkKc3RyaW5nIGluZml4VG9Qb3N0Zml4KGNvbnN0IHN0cmluZyYgaW5maXgpIHsKICAgIHN0YWNrPGNoYXI+IG9wZXJhdG9yczsKICAgIHN0cmluZ3N0cmVhbSBvdXRwdXQ7CgogICAgZm9yIChzaXplX3QgaSA9IDA7IGkgPCBpbmZpeC5sZW5ndGgoKTsgaSsrKSB7CiAgICAgICAgY2hhciB0b2tlbiA9IGluZml4W2ldOwoKICAgICAgICAvLyDQr9C60YnQviDRgdC40LzQstC+0Lsg4oCUINGH0LjRgdC70L4g0LDQsdC+INC70ZbRgtC10YDQsCwg0LTQvtC00LDRlNC80L4g0LnQvtCz0L4g0YMg0LLQuNGF0ZbQtNC90LjQuSDRgNGP0LTQvtC6CiAgICAgICAgaWYgKGlzYWxudW0odG9rZW4pKSB7CiAgICAgICAgICAgIG91dHB1dCA8PCB0b2tlbjsKICAgICAgICB9CiAgICAgICAgLy8g0K/QutGJ0L4g0YHQuNC80LLQvtC7IOKAlCDQvtC/0LXRgNCw0YLQvtGACiAgICAgICAgZWxzZSBpZiAoaXNPcGVyYXRvcih0b2tlbikpIHsKICAgICAgICAgICAgd2hpbGUgKCFvcGVyYXRvcnMuZW1wdHkoKSAmJiBwcmVjZWRlbmNlW29wZXJhdG9ycy50b3AoKV0gPj0gcHJlY2VkZW5jZVt0b2tlbl0pIHsKICAgICAgICAgICAgICAgIG91dHB1dCA8PCAnICcgPDwgb3BlcmF0b3JzLnRvcCgpOwogICAgICAgICAgICAgICAgb3BlcmF0b3JzLnBvcCgpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIG91dHB1dCA8PCAnICc7CiAgICAgICAgICAgIG9wZXJhdG9ycy5wdXNoKHRva2VuKTsKICAgICAgICB9CiAgICAgICAgLy8g0K/QutGJ0L4g0YHQuNC80LLQvtC7IOKAlCDQstGW0LTQutGA0LjRgtCwINC00YPQttC60LAsINC00L7QtNCw0ZTQvNC+INCyINGB0YLQtdC6CiAgICAgICAgZWxzZSBpZiAodG9rZW4gPT0gJygnKSB7CiAgICAgICAgICAgIG9wZXJhdG9ycy5wdXNoKHRva2VuKTsKICAgICAgICB9CiAgICAgICAgLy8g0K/QutGJ0L4g0YHQuNC80LLQvtC7IOKAlCDQt9Cw0LrRgNC40YLQsCDQtNGD0LbQutCwLCDQvtCx0YDQvtCx0LvRj9GU0LzQviDRgdGC0LXQugogICAgICAgIGVsc2UgaWYgKHRva2VuID09ICcpJykgewogICAgICAgICAgICB3aGlsZSAoIW9wZXJhdG9ycy5lbXB0eSgpICYmIG9wZXJhdG9ycy50b3AoKSAhPSAnKCcpIHsKICAgICAgICAgICAgICAgIG91dHB1dCA8PCAnICcgPDwgb3BlcmF0b3JzLnRvcCgpOwogICAgICAgICAgICAgICAgb3BlcmF0b3JzLnBvcCgpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIG9wZXJhdG9ycy5wb3AoKTsgLy8g0JLQuNC00LDQu9GP0ZTQvNC+ICcoJwogICAgICAgIH0KICAgIH0KCiAgICAvLyDQktC40YLRj9Cz0YPRlNC80L4g0LfQsNC70LjRiNC60Lgg0L7Qv9C10YDQsNGC0L7RgNGW0LIg0LfRliDRgdGC0LXQutGDCiAgICB3aGlsZSAoIW9wZXJhdG9ycy5lbXB0eSgpKSB7CiAgICAgICAgb3V0cHV0IDw8ICcgJyA8PCBvcGVyYXRvcnMudG9wKCk7CiAgICAgICAgb3BlcmF0b3JzLnBvcCgpOwogICAgfQoKICAgIHJldHVybiBvdXRwdXQuc3RyKCk7Cn0KCmludCBtYWluKCkgewogICAgc3RyaW5nIGluZml4ID0gIjMrNCoyLygxLTUpIjsKICAgIGNvdXQgPDwgItCG0L3RhNGW0LrRgdC90LjQuSDQt9Cw0L/QuNGBOiAiIDw8IGluZml4IDw8IGVuZGw7CiAgICBjb3V0IDw8ICLQn9C+0YHRgtGE0ZbQutGB0L3QuNC5INC30LDQv9C40YE6ICIgPDwgaW5maXhUb1Bvc3RmaXgoaW5maXgpIDw8IGVuZGw7CiAgICByZXR1cm4gMDsKfQo=