#include <iostream>
#include <stack>
#include <algorithm> // For reverse function
using namespace std;
// Function to return the precedence of operators
int precedence(char op) {
if (op == '^')
return 3;
else if (op == '*' || op == '/')
return 2;
else if (op == '+' || op == '-')
return 1;
return -1;
}
// Function to convert infix to postfix
string infixToPostfix(string infix) {
stack<char> s;
string postfix = "";
for (int i = 0; i < infix.length(); i++) {
char c = infix[i];
// If the character is an operand, add it to the postfix expression
if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
postfix += c;
}
// If the character is '(', push it to the stack
else if (c == '(') {
s.push(c);
}
// If the character is ')', pop until '(' is encountered
else if (c == ')') {
while (!s.empty() && s.top() != '(') {
postfix += s.top();
s.pop();
}
if (!s.empty()) s.pop(); // Pop '(' from stack
}
// If the character is an operator
else {
while (!s.empty() && precedence(s.top()) >= precedence(c)) {
postfix += s.top();
s.pop();
}
s.push(c);
}
}
// Pop all remaining operators from the stack
while (!s.empty()) {
postfix += s.top();
s.pop();
}
return postfix;
}
// Function to convert infix to prefix
string infixToPrefix(string infix) {
// Step 1: Reverse the infix expression
reverse(infix.begin(), infix.end());
// Step 2: Replace '(' with ')' and vice versa
for (int i = 0; i < infix.length(); i++) {
if (infix[i] == '(') {
infix[i] = ')';
} else if (infix[i] == ')') {
infix[i] = '(';
}
}
// Step 3: Convert the modified infix expression to postfix
string postfix = infixToPostfix(infix);
// Step 4: Reverse the postfix expression to get the prefix expression
reverse(postfix.begin(), postfix.end());
return postfix;
}
int main() {
string infix;
cout << "Enter infix expression: ";
cin >> infix;
string prefix = infixToPrefix(infix);
cout << "Prefix expression: " << prefix << endl;
return 0;
}
