#include <iostream>
#include <stack>
#include <sstream>
class TreeNode {
public:
char data;
TreeNode* left;
TreeNode* right;
TreeNode(char value) : data(value), left(nullptr), right(nullptr) {}
};
class TreeConverter {
private:
TreeNode* root;
void buildTreeFromInorder(std::string& inorder) {
std::stack<TreeNode*> s;
TreeNode* current = nullptr;
for (char ch : inorder) {
if (isalpha(ch)) {
current = new TreeNode(ch);
s.push(current);
} else {
TreeNode* right = s.top();
s.pop();
TreeNode* left = s.top();
s.pop();
current = new TreeNode(ch);
current->left = left;
current->right = right;
s.push(current);
}
}
root = current;
}
void postOrderTraversal(TreeNode* node, std::stringstream& ss) {
if (node == nullptr)
return;
postOrderTraversal(node->left, ss);
postOrderTraversal(node->right, ss);
ss << node->data;
}
public:
TreeConverter(const std::string& inorder) : root(nullptr) {
buildTreeFromInorder(const_cast<std::string&>(inorder));
}
std::string convertToPostorder() {
std::stringstream ss;
postOrderTraversal(root, ss);
return ss.str();
}
};
int main() {
std::string inorder_expression;
std::cout << "Enter the inorder expression: ";
std::cin >> inorder_expression;
TreeConverter converter(inorder_expression);
std::string postorder_expression = converter.convertToPostorder();
std::cout << "Postorder expression: " << postorder_expression << std::endl;
return 0;
}