Postfix to Infix Converter Online – Step by Step Evaluation

How to Convert Postfix to Infix Expression Using a Stack

A postfix expression (also known as Reverse Polish Notation or RPN) is a notation in which the operators follow their operands. For example, the postfix expression AB+ corresponds to the infix expression (A+B). Our free postfix to infix converter online above lets you input any valid postfix expression and instantly see the equivalent infix form along with a detailed stack trace.

Postfix to Infix Conversion Algorithm (Stack-Based)

The algorithm for converting postfix to infix uses a simple stack:

1. Initialize an empty stack.
2. Scan the postfix expression from left to right.
3. For each token: ◦ If the token is an operand, push it onto the stack. ◦ If the token is an operator: pop two elements (let’s call them b and a), form the string (a operator b), and push the result back onto the stack.
4. After processing all tokens, the final element in the stack is the complete infix expression.

Postfix to Infix Example: AB+C*

1. Read A (operand) → push. Stack: [A]
2. Read B (operand) → push. Stack: [A, B]
3. Read + (operator) → pop B and A, form (A+B), push. Stack: [(A+B)]
4. Read C (operand) → push. Stack: [(A+B), C]
5. Read * (operator) → pop C and (A+B), form ((A+B)*C), push. Stack: [((A+B)*C)]

Final Infix Expression: ((A+B)*C)

Time Complexity of Postfix to Infix Conversion

The time complexity is O(n) where n is the number of tokens. Each token is processed exactly once with constant-time stack operations (push/pop), making this algorithm highly efficient.

Postfix to Infix Conversion Code in C

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

#define MAX 100

char stack[MAX][MAX];
int top = -1;

void push(char *item) {
    if (top < MAX - 1) {
        top++;
        strcpy(stack[top], item);
    }
}

char* pop() {
    if (top >= 0) return stack[top--];
    return NULL;
}

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

void postfixToInfix(char *postfix) {
    char operand1[MAX], operand2[MAX], temp[MAX];
    
    for (int i = 0; postfix[i] != '\0'; i++) {
        if (isalnum(postfix[i])) {
            char str[2] = {postfix[i], '\0'};
            push(str);
        } else if (isOperator(postfix[i])) {
            strcpy(operand1, pop());
            strcpy(operand2, pop());
            sprintf(temp, "(%s%c%s)", operand2, postfix[i], operand1);
            push(temp);
        }
    }
    printf("Infix Expression: %s\n", pop());
}

int main() {
    char postfix[] = "AB+C*";
    postfixToInfix(postfix);
    return 0;
}

Conclusion

The conversion from postfix to infix is a fundamental concept in computer science, especially in expression parsing, compiler design, and calculator implementations. By utilizing a stack and understanding the simple algorithm, you can effectively convert between notations. Our free postfix to infix converter online tool makes this process instant and educational with its step-by-step stack trace visualization.