#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAX 105

char stack[MAX];
int top = -1;
void push(char c) {
    stack[++top] = c;
}
char pop() {
    return stack[top--];
}
char peek() {
    return stack[top];
}
int precedence(char op) {
    switch (op) {
        case '^': return 3;
        case '*': case '/': return 2;
        case '+': case '-': return 1;
        default: return 0;
    }
}
int isOperator(char c) {
    return (c=='+' || c=='-' || c=='*' || c=='/' || c=='^');
}
int isValidChar(char c) {
    return (isdigit(c) || isOperator(c) || c=='(' || c==')');
}
int validate(const char *exp) {
    int balance = 0;
    for (int i = 0; exp[i]; i++) {
        if (!isValidChar(exp[i])) return 0;
        if (exp[i] == '(') balance++;
        else if (exp[i] == ')') balance--;
        if (balance < 0) return 0;
    }
    return balance == 0;
}
int main() {
    char exp[MAX];
    if (!fgets(exp, sizeof(exp), stdin)) return 0;
    exp[strcspn(exp, "\n")] = 0;

    if (!validate(exp)) {
        printf("Invalid input");
        return 0;
    }
    char output[MAX];
    int k = 0;
    for (int i = 0; exp[i]; i++) {
        char c = exp[i];
        if (isdigit(c)) {
            output[k++] = c;
        }
        else if (c == '(') {
            push(c);
        }
        else if (c == ')') {
            while (top != -1 && peek() != '(') {
                output[k++] = pop();
            }
            pop(); 
        }
        else if (isOperator(c)) {
            while (top != -1 && precedence(peek()) >= precedence(c)) {
                if (peek() == '(') break;
                output[k++] = pop();
            }
            push(c);
        }
    }
    while (top != -1) {
        if (peek() == '(' || peek() == ')') {
            printf("Invalid input");
            return 0;
        }
        output[k++] = pop();
    }
    output[k] = '\0';
    printf("%s", output);
    return 0;
}
[3:42 pm, 10/09/2025] Navii: 1