Expression tree using a stack

A binary expression tree represents an arithmetic expression: leaves hold operands, and internal nodes hold operators. If you already have correct postfix (RPN), one classic approach uses a stack of pointers to tree nodes. The same push / pop pattern also works with a stack of short strings: each slot holds the parenthesized infix for a partial expression—no malloc for nodes, and the final pop is the full infix string (equivalent to an inorder print of the implicit tree).

1) What the tree looks like

For a binary operator, the infix form (left op right) becomes a node whose character is op, with subtrees for left and right. A single variable or number is a leaf (both child pointers NULL).

The postfix string ab+c* describes (a + b) * c: first build the + tree for a and b, then apply * with that tree on the left and c on the right.

2) Building from postfix

Scan the postfix string from left to right. Use a stack where each entry is a partial infix string (one operand or a parenthesized sub-expression). That mirrors the tree view: each stack slot corresponds to the infix form of a subtree.

Time is O(n) for n tokens; space depends on string lengths (nested parentheses can make intermediate strings long—bounded by MAX in the program below).

3) Example in C

The program reads a postfix expression with scanf("%s", ...). A 2D char array acts as a stack of strings: each row holds one partial expression. Operands are pushed as single-character strings; each operator pops the right and left operands, builds (left op right) with sprintf, and pushes the combined string. The final pop is printed as the infix form.

#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAX 100

// Stack of strings
char stack[MAX][MAX];
int top = -1;

// Push string into stack
void push(char str[]) {
    top++;
    strcpy(stack[top], str);
}

// Pop string from stack
char* pop() {
    return stack[top--];
}

// Check operator
int isOperator(char ch) {
    return (ch=='+' || ch=='-' || ch=='*' || ch=='/');
}

int main() {
    char postfix[MAX];
    char op1[MAX], op2[MAX], temp[MAX];

    printf("Enter postfix expression: ");
    scanf("%s", postfix);

    for (int i = 0; postfix[i] != '\0'; i++) {
        char ch = postfix[i];

        // If operand → push as string
        if (isalnum(ch)) {
            temp[0] = ch;
            temp[1] = '\0';
            push(temp);
        }
        // If operator → combine two operands
        else if (isOperator(ch)) {
            strcpy(op2, pop());
            strcpy(op1, pop());

            // Create new infix expression
            sprintf(temp, "(%s%c%s)", op1, ch, op2);

            push(temp);
        }
    }

    printf("Infix Expression: %s\n", pop());

    return 0;
}

pop() returns a pointer into stack; strcpy copies out before the next push overwrites that slot. Check top before pop for a valid postfix expression, cap input length (prefer fgets over bare scanf("%s")), and ensure sprintf results fit in temp. Deeply nested expressions can exceed fixed MAX buffers.

Trace for postfix ab+c*

The stack lists partial infix strings from bottom → top (top is the rightmost entry).

Key points

4) Trade-offs

• Pros — Simple arrays and strcpy/sprintf; one linear pass from postfix; easy to print parenthesized infix.
• Cons — Fixed buffer sizes; repeated string copying; for heavy rewriting or analysis, explicit tree nodes are often clearer.

See Stack applications for where expression stacks appear, and Infix to postfix if you need the RPN string first.