#include #include 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 oprStack; int len = static_cast(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 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; }

Public snippets