Untitled

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdbool.h>

typedef struct S {
	char num[1000];
	bool add, sub, mul, div;
} S;

bool isoper(S s) {
	return s.num[0] == '\0';
}

S get(char c) {
	S s;
	s.num[0] = '\0';
	s.add = s.sub = s.mul = s.div = false;
	if(c == '+' || c == '-' || c == '*' || c == '/') {
		if(c == '+') {
			s.add = true;
		} else if(c == '-') {
			s.sub = true;
		} else if(c == '*') {
			s.mul = true;
		} else {
			s.div = true;
		}
	} else {
		s.num[0] = c;
		s.num[1] = '\0';
	}
	return s;
}

S addBracket(S s) {
	int n = strlen(s.num);
	if(n == 1) {
		return s;
	}
	for(int i = n; i > 0; --i) {
		s.num[i] = s.num[i - 1];
	}
	s.num[0] = '(';
	s.num[n + 1] = ')';
	s.num[n + 2] = '\0';
	s.add = s.sub = s.mul = s.div = false;
	return s;
}

int n;
char s[1000];
S stk[1000];
int sz = 0;

int main() {
	scanf("%s", s);
	n = strlen(s);
	for(int i = 0; i < n; ++i) {
		stk[sz++] = get(s[i]);
		while(sz >= 3 && !isoper(stk[sz - 1]) && !isoper(stk[sz - 2])) {
			S B = stk[--sz];
			S A = stk[--sz];
			S tmp = stk[--sz];
			assert(tmp.add + tmp.sub + tmp.mul + tmp.div == 1);
			char op;
			if(tmp.add) {
				op = '+';
			} else if(tmp.sub) {
				op = '-';
			} else if(tmp.mul) {
				op = '*';
			} else {
				op = '/';
			}
			S res;
			if(op == '-') {
				if(B.add || B.sub) {
					B = addBracket(B);
				}
			} else if(op == '/') {
				B = addBracket(B);
				if(A.add || A.sub) {
					A = addBracket(A);
				}
			} else if(op == '*') {
				if(A.add || A.sub) {
					A = addBracket(A);
				}
				if(B.add || B.sub) {
					B = addBracket(B);
				}
			}
			sprintf(res.num, "%s%c%s", A.num, op, B.num);
			res.add = A.add || B.add || op == '+';
			res.sub = A.sub || B.sub || op == '-';
			res.mul = A.mul || B.mul || op == '*';
			res.div = A.div || B.div || op == '/';
			stk[sz++] = res;
		}
	}
	assert(sz == 1);
	puts(stk[0].num);
	return 0;
}