Parentheses Removal Function

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

/*
 * Helper Function
 */
int prec(char ch) {
    if (ch == '+' || ch == '-') return 1;
    if (ch == '*' || ch == '/') return 2;
    if (ch == '^') return 3;
    return 0;
}

int prec(const string &str) {
    if (str == "+" || str == "-") return 1;
    if (str == "*" || str == "/") return 2;
    if (str == "^") return 3;
    return 0;
}

string removeSpaces(string str) {
    str.erase(remove(str.begin(), str.end(),' '),str.end());
    return str;
}

bool replace(string& str, const string& from, const string& to) {
    size_t start_pos = str.find(from);
    if(start_pos == string::npos)
        return false;
    str.replace(start_pos, from.length(), to);
    return true;
}

/*
 * Shunting Yard Algorithm Implement
 */
string infixToPostfix(string infix) {
    string postfix;
    stack<char> oprStack;

    int len = static_cast<int>(infix.length());
    for (int i = 0; i < len; i++) {
        // The scanned character is an operand. We need to add it to the postfix string.
        // Be care of the multi-digit number
        if (isalpha(infix[i]) || isdigit(infix[i])) {
            if (isalpha(infix[i + 1]) || isdigit(infix[i + 1]) || infix[i + 1] == '(') {
                postfix += infix[i];
            } else {
                postfix += infix[i];
                postfix += ' ';
            }
        }

        // The scanned character is '(', push it to the stack.
        // Be care of the negtive number
        else if (infix[i] == '(') {
            if (infix[i + 1] != '-') {
                oprStack.push('(');
            } else {
                oprStack.push('(');
                postfix += infix[i + 1];
                i++;
            }
        }

        else if (infix[i] == '-' && i == 0) {
            postfix += infix[i];
        }

        // The scanned character is ')', pop it out to string from the stack
        // until an '(' is encountered.
        else if (infix[i] == ')') {
            while (!oprStack.empty() && oprStack.top() != '(') {
                postfix += oprStack.top();
                postfix += ' ';
                oprStack.pop();
            }
            if (oprStack.top() == '(') {
                oprStack.pop();
            }
        }

        // The scanned character is operator
        // Be careful of '/' and '-'
        else if ((infix[i] == '/' || infix[i] == '*') && infix[i + 1] == '-') {
            oprStack.push(infix[i]);
            postfix += infix[i + 1];
            i++;
        }

        else {
            while(!oprStack.empty() && prec(infix[i]) <= prec(oprStack.top())) {
                postfix += oprStack.top();
                postfix += ' ';
                oprStack.pop();
            }
            oprStack.push(infix[i]);
        }

    }
    // Pop all the remaining elements from the stack
    while (!oprStack.empty()) {
        postfix += oprStack.top();
        postfix += ' ';
        oprStack.pop();
    }

    return postfix;

}

/*
 * postfixToInfix
 */
string postfixToInfix(const string &postfix) {
    int lpre, rpre = 4;
    string infix, temp;
    stack<string> postfixStack;

    // Get the exprStack
    stringstream s (postfix);
    while(s >> temp) {
        if (temp != "+" && temp != "-" && temp != "*" && temp != "/" ) {
            postfixStack.push(temp);
            lpre = rpre;
            rpre = 4;
        } else if (temp == "+") {
            string rexpr = postfixStack.top();
            postfixStack.pop();
            string lexpr = postfixStack.top();
            postfixStack.pop();

            postfixStack.push(lexpr + temp + rexpr);
            lpre = rpre;
            rpre = 1;
        } else if (temp == "-") {
            string rexpr = postfixStack.top();
            postfixStack.pop();
            string lexpr = postfixStack.top();
            postfixStack.pop();

            if (rpre <= prec(temp)) {
                rexpr = "(" + rexpr + ")";
            }
            postfixStack.push(lexpr + temp + rexpr);
            lpre = rpre;
            rpre = 1;
        } else if (temp == "*") {
            string rexpr = postfixStack.top();
            postfixStack.pop();
            string lexpr = postfixStack.top();
            postfixStack.pop();

            if (rpre < prec(temp)) {
                rexpr = "(" + rexpr + ")";
            }

            if (lpre < prec(temp)) {
                lexpr = "(" + lexpr + ")";
            }

            postfixStack.push(lexpr + temp + rexpr);
            lpre = rpre;
            rpre = 2;
        } else if (temp == "/") {
            string rexpr = postfixStack.top();
            postfixStack.pop();
            string lexpr = postfixStack.top();
            postfixStack.pop();

            if (rpre <= prec(temp)) {
                rexpr = "(" + rexpr + ")";
            }

            if (lpre < prec(temp)) {
                lexpr = "(" + lexpr + ")";
            }

            postfixStack.push(lexpr + temp + rexpr);
            lpre = rpre;
            rpre = 2;
        }
    }

    return postfixStack.top();
}

/*
 * Main Function
 */
int main() {
    string expr;
    while (getline(cin, expr)) {
        expr = removeSpaces(expr);
        replace(expr, ")(", ")*(");
        cout << postfixToInfix(infixToPostfix(expr)) << endl;
    }
    return 0;
}