#include #include #include #include #include using namespace std; int precedence(char c) { if(c == '^') return 3; else if(c == '*' || c == '/') return 2; else if(c == '+' || c == '-') return 1; else return -1; } void change_braces(string &st) { int l = st.size(); for(int i=0;i st,string infix) { string prefix; reverse(infix.begin(),infix.end()); change_braces(infix); int l = infix.size(); for(int i=0;i= 'a' && infix[i] <= 'z') || (infix[i] >= 'A' && infix[i] <= 'Z')|| (infix[i] >= '0' && infix[i] <= '9')) prefix += infix[i]; // if left parentheses else if(infix[i] == '(') st.push(infix[i]); // if right parentheses else if(infix[i] == ')') { while(st.top() != '(' && !st.empty()) { prefix += st.top(); st.pop(); } st.pop(); //for simply removing left parentheses } //if operator case else { // operator when stack empty if(st.empty()) st.push(infix[i]); else { // incoming operator greater or equal precedence if(precedence(infix[i]) > precedence(st.top())) st.push(infix[i]); //equal precedence in case of ^ else if(precedence(infix[i]) == precedence(st.top()) && infix[i] == '^') { while(precedence(infix[i]) == precedence(st.top()) && infix[i] == '^') { prefix += st.top(); st.pop(); } st.push(infix[i]); //pushing ^ } // incoming operator greater or equal precedence else if(precedence(infix[i]) == precedence(st.top())) st.push(infix[i]); else { while(!st.empty() &&(precedence(infix[i]) < precedence(st.top()))) { prefix += st.top(); st.pop(); } st.push(infix[i]); }//end of inner if else } //end of inner if 2 }//else of main if block }// end of main for loop block //now making the stack empty while(!st.empty()) { prefix += st.top(); st.pop(); } reverse(prefix.begin(),prefix.end()); return prefix; } int result(string prefix) { stack st; int l = prefix.size(); for(int i=l-1;i>=0;i--) { if(prefix[i] >='0' && prefix[i] <= '9') { int val = prefix[i]-48; st.push(val); } else { int opd1 = st.top(); st.pop(); int opd2 = st.top(); st.pop(); int res; if(prefix[i] == '+') res = opd1 + opd2; else if(prefix[i] == '-') res = opd1 - opd2; else if(prefix[i] == '*') res = opd1 * opd2; else if(prefix[i] == '/') res = opd1 / opd2; else if(prefix[i] == '^') { res = pow(opd1,opd2); } st.push(res); } } return st.top(); } string toInfix(string prefix) { stack st; int l = prefix.size(); for(int i=l-1;i>=0;i--) { // if operand if((prefix[i] >= 'a' && prefix[i] <= 'z') || (prefix[i] >= 'A' && prefix[i] <= 'Z')|| (prefix[i] >= '0' && prefix[i] <= '9')) { string x = to_string(prefix [i]); st.push(x); } else { string opd1 = st.top(); st.pop(); string opd2 = st.top(); st.pop(); string res,symbol = to_string( prefix[i]); if(symbol == "+") res = "("+opd1+"+"+opd2+")"; else if(symbol== "-") res = "("+opd1+"-"+opd2+")"; else if(symbol == "*") res = "("+opd1+"*"+opd2+")"; else if(symbol == "/") res = "("+opd1+"/"+opd2+")"; else if(symbol == "^") res = "("+opd1+"^"+opd2+")"; st.push(res); } } return st.top(); } int main() { cout << "Infix to Prefix\n"; string infix,p; stackst; cout<<"Enter infix :: "; cin>>infix; p = toPrefix(st,infix); cout<< "Prefix :: "<