fork download
copy 
  1. #include <iostream>
  2. #include <stack>
  3. #include <string>
  4. using namespace std;
  5. // 1. Structure for a Binary Tree Node
  6. struct Node {
  7.   char value;
  8.   Node *left;
  9.   Node *right;
  10.   // Constructor to initialize a new node
  11.   Node(char val) {
  12.     value = val;
  13.     left = right = nullptr;
  14.   }
  15. };
  16. // 2. Helper function to check if a character is an operator
  17. bool isOperator(char c) {
  18.   return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^');
  19. }
  20. // 3. Function to construct an Expression Tree from a Postfix string
  21. Node *constructTree(string postfix) {
  22.   stack<Node *> st;
  23.   Node *t, *t1, *t2;
  24.   // Traverse through every character of the postfix expression
  25.   for (int i = 0; i < postfix.length(); i++) {
  26.     // If the character is an OPERAND, create a node and push to Stack:
  27.     if (!isOperator(postfix[i])) {
  28.       t = new Node(postfix[i]);
  29.       st.push(t);
  30.     }
  31.     // If the character is an OPERATOR:
  32.     else {
  33.       t = new Node(postfix[i]);
  34.       // Pop the top two nodes from the stack to serve as children
  35.       // The first popped node becomes the RIGHT child (due to LIFO property)
  36.       t1 = st.top();
  37.       st.pop();
  38.       // The second popped node becomes the LEFT child
  39.       t2 = st.top();
  40.       st.pop();
  41.       // Assign children to the operator node
  42.       t->right = t1;
  43.       t->left = t2;
  44.       // Push the operator node (now a sub-tree) back onto the stack
  45.       st.push(t);
  46.     }
  47.   }
  48.   // The final remaining node in the stack is the Root of the entire tree
  49.   t = st.top();
  50.   st.pop();
  51.   return t;
  52. }
  53. // 4. Function for Inorder Traversal (Left - Root - Right) to print the Infix
  54. // expression
  55. void inorder(Node *t) {
  56.   if (t != nullptr) {
  57.     inorder(t->left);
  58.     cout << t->value << " ";
  59.     inorder(t->right);
  60.   }
  61. }
  62.  
  63. int main() {
  64.   // Equivalent expression: (A + B) - (E * F * G)
  65.   string postfix = "AB+EF*G*-";
  66.   cout << "Input Postfix string: " << postfix << endl;
  67.   // Build the tree
  68.   Node *root = constructTree(postfix);
  69.   // Traverse the tree to verify the result
  70.   cout << "Infix expression (Inorder Traversal): ";
  71.   inorder(root);
  72.   cout << endl;
  73.   return 0;
  74. }
  75.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Input Postfix string: AB+EF*G*-
Infix expression (Inorder Traversal): A + B - E * F * G
https://ideone.com/racA4j
language:
C++ (gcc 8.3)
created:
19 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!