#include <iostream>
#include <stack>
#include <string>
using namespace std;
struct Node {
char data;
Node* left;
Node* right;
};
bool isOperator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/');
}
Node* newNode(char data) {
Node* node = new Node;
node->data = data;
node->left = node->right = nullptr;
return node;
}
string convertPreToPost(const string& preExpr) {
stack<Node*> stack;
int length = preExpr.length();
for (int i = length - 1; i >= 0; i--) {
if (!isOperator(preExpr[i])) {
Node* operand = newNode(preExpr[i]);
stack.push(operand);
} else {
Node* operatorNode = newNode(preExpr[i]);
Node* operand1 = stack.top();
stack.pop();
Node* operand2 = stack.top();
stack.pop();
operatorNode->left = operand1;
operatorNode->right = operand2;
stack.push(operatorNode);
}
}
Node* root = stack.top();
stack.pop();
string postExpr = "";
stack<Node*> postStack;
postStack.push(root);
while (!postStack.empty()) {
Node* temp = postStack.top();
postStack.pop();
postExpr += temp->data;
if (temp->left)
postStack.push(temp->left);
if (temp->right)
postStack.push(temp->right);
}
reverse(postExpr.begin(), postExpr.end());
return postExpr;
}
int main() {
string preExpr;
cout << "Enter the prefix expression: ";
cin >> preExpr;
string postExpr = convertPreToPost(preExpr);
cout << "Equivalent postfix expression: " << postExpr << endl;
return 0;
}