Parentheses Removal Function
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201
#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;
}
Cpp
INFO