What is infix, prefix and postfix expression? Explain with example.

In computer science and mathematics, expressions can be written in multiple notations that differ only in where the operator is placed relative to its operands. The three rigorously equivalent, machine- and human-relevant styles are infix (operator between operands), prefix (operator before operands; also called Polish notation), and postfix (operator after operands; also called Reverse Polish Notation (RPN)). Although all three describe identical computation, they serve distinct goals: infix maximizes human readability but requires rules for operator precedence and associativity, while prefix and postfix remove ambiguity, eliminate parentheses, and map directly to simple stack-based or recursive evaluation strategies used in interpreters, compilers, calculators, and expression-tree engines. A technically precise definition views an expression as a well-formed string over an operator alphabet and an operand alphabet, with a grammar that enforces arity and binding. Infix grammars need precedence tables; prefix and postfix grammars encode precedence implicitly by placement. Knowing how to convert among these notations is foundational for DSA learners because it underpins compiler parsing (shunting-yard and precedence-climbing), evaluation engines, and the design of data structures such as expression trees. In this article, you will learn exact definitions that sound simple, see step-by-step conversions, evaluate examples, reason about complexity, and implement Java code that converts and evaluates all three notations using stacks, with clear, practical explanations that remain formal enough for exam settings and interviews.

The Crust (TL;DR) — Read This If You’re In a Hurry

• Infix: Operator between operands (A + B). Needs precedence/associativity and parentheses; human-friendly, machine-ambiguous.
• Prefix (Polish): Operator before operands (+ A B). No parentheses needed; evaluate right-to-left or with recursion; compiler-friendly.
• Postfix (RPN): Operator after operands (A B +). No parentheses; evaluate left-to-right using a stack; calculator- and VM-friendly.
• Equivalence: (A + B) * C ≡ Infix: (A + B) * C, Prefix: * + A B C, Postfix: A B + C *
• Core idea: In prefix/postfix, operator position encodes precedence; operands retain their mutual order across all three notations.
• Conversions: Infix→Postfix via shunting-yard; Infix→Prefix via reverse+shunting-yard+reverse; Prefix/Postfix conversions via stack.
• Evaluation: Postfix uses a stack (scan L→R); Prefix uses a stack or recursion (scan R→L); Infix typically converts then evaluates.
• Use cases: Infix for code and math texts; Prefix for parsers/formal logic; Postfix for stacks, bytecode, calculators, and VMs.
• Rule of thumb: Show users infix; implement engines with prefix/postfix; convert at the boundary.

What Is an Infix Expression?

An infix expression places each operator between its two operands, following the familiar arithmetic convention taught in school, e.g., A + B, X * Y, or (M – N) / P. Formally, a binary infix term has the shape <operand> <operator> <operand>, while nested structures are formed via parentheses to override or make explicit the precedence (binding power) and associativity (tie-breaking direction) of operators. Typical precedence is ^ (highest), then * and /, then + and -, with left associativity for +, -, *, /. Because the same string can parse in multiple ways without parentheses, infix is ambiguous to machines and requires either a grammar with precedence levels or a conversion step before evaluation. For example, A + B * C must be interpreted as A + (B * C), not (A + B) * C, due to precedence. In practical compilers, infix is parsed into an abstract syntax tree (AST) that captures operator binding explicitly; evaluation then traverses the AST, or the AST is lowered to a stack-based intermediate form. While infix is extremely readable for humans and aligns with most programming language expressions, its ambiguity makes pure direct evaluation cumbersome; hence, engines often translate it into prefix or postfix before evaluation.

Infix Example and Evaluation Steps

• Expression: (3 + 4) * (6 – 2)
• Apply precedence/parentheses:
  1. Evaluate inner sums/differences first: 3 + 4 = 7 and 6 – 2 = 4.
  2. Multiply the results: 7 * 4 = 28.
• Key observations:
  • Parentheses disambiguate and override precedence.
  • Without parentheses, 3 + 4 * 5 means 3 + (4 * 5) = 23.
  • For machines, infix typically becomes a tree or is converted to postfix/prefix.

What Is a Postfix (Reverse Polish) Expression?

A postfix expression (also called Reverse Polish Notation, RPN) places each operator after its operands: e.g., AB+ for A + B and ABC*+ for A + (B * C). Technically, postfix linearizes the parse tree such that operands appear in left-to-right order and each operator follows the precise subexpressions it must consume, eliminating the need for parentheses and precedence tables. Postfix is especially amenable to a stack-based evaluation strategy: scan left-to-right; push operands; when an operator appears, pop the top required number of operands (two for binary operators), apply the operator, and push the result. This direct mapping underlies stack machine VMs, bytecode interpreters, and classic calculators. The notation is unambiguous, compact, and enables single-pass evaluation with predictable O(n) time for n tokens. For example, 3 4 + 5 * evaluates by pushing 3, pushing 4, applying + to produce 7, pushing 5, applying * to produce 35. In DSA and compiler courses, postfix is the canonical target of the shunting-yard algorithm that converts infix to postfix while respecting precedence and associativity by temporarily holding operators on a stack and emitting operands immediately. Because postfix embeds order explicitly, it is a preferred intermediate representation for interpreters and low-level expression engines.

Postfix Example and Step-by-step Evaluation

• Expression: 3 4 + 6 2 – *
• Steps:
  1. Push 3; push 4; see +; pop 4 and 3; compute 7; push 7.
  2. Push 6; push 2; see -; pop 2 and 6; compute 4; push 4.
  3. See *; pop 4 and 7; compute 28; push 28.
  4. End of input: top of stack is 28.
• Notes:
  • Operands keep left-to-right order; only operators move.
  • Single linear pass; no parentheses or precedence rules needed at runtime.

What Is a Prefix (Polish) Expression?

A prefix expression (also called Polish notation) places each operator before its operands: e.g., +AB for A + B and *+ABC for (A + B) * C. In a precise sense, prefix is a pre-order linearization of the expression tree, where the operator precedes the subtrees it operates on. Like postfix, prefix removes ambiguity and parentheses, but its natural evaluation scans right-to-left using a stack or uses recursion to consume operator-operand groups. For example, to evaluate * + 3 4 5, process from right to left: push 5, push 4, push 3; encounter +, pop 3 and 4, compute 7, push 7; encounter *, pop 7 and 5, compute 35. Prefix is elegant in parsers because its structure mirrors function application: + a b is analogous to an n-ary function call plus(a, b) without commas or parentheses. This makes prefix useful in logic systems and in compiler front-ends that reduce expression parsing to structured recursive descent. Like postfix, prefix is O(n) to evaluate linearly with a stack and is fully parenthesis-free while preserving the operand order inherited from the original infix.

Prefix Example and Step-by-step Evaluation

• Expression: – * + 2 3 4 5
• Steps (scan right-to-left):
  1. Push 5; push 4; push 3; push 2.
  2. See +; pop 2 and 3 → 5; push 5.
  3. See *; pop 5 and 4 → 20; push 20.
  4. See -; pop 20 and 5 → 15; push 15.
  5. End: result 15.
• Notes:
  • Prefix and postfix are mirror images in evaluation direction.
  • Both eliminate parentheses and precedence handling at runtime.

Converting Between Infix, Prefix, and Postfix

Converting between notations relies on preserving the relative order of operands and repositioning operators to encode precedence. The canonical infix→postfix conversion uses the shunting-yard algorithm: scan tokens left-to-right, append operands immediately to output, and manage operator precedence/associativity using a stack so that higher-precedence operators are emitted earlier. Infix→prefix can be obtained by reversing the infix string (swap parentheses), applying the same shunting-yard logic (with a slight precedence tie tweak), and reversing the result, or by directly building an expression tree and then emitting pre-order. Prefix↔postfix conversion is naturally stack-based: read tokens, push operands, and when an operator is encountered, pop the correct number of subexpressions and recompose in the other notation. Across these conversions, two invariants hold: (1) the operand order is preserved relative to each other; (2) parentheses vanish in the prefix/postfix outputs because operator placement now encodes binding. Practically, many compilers parse infix to an AST, then emit either prefix or postfix for interpretation or code generation, and many interview problems expect you to implement infix→postfix and postfix evaluation with a stack in O(n) time and O(n) auxiliary space (worst-case when many operators are stacked).

Steps: Infix to Postfix (Shunting-yard)

1. Initialize an empty operator stack and an empty output list.
2. Scan tokens left-to-right:
   • If operand, append to output.
   • If ‘(‘, push to stack.
   • If ‘)’, pop stack to output until ‘(‘ is popped.
   • If operator op, then while stack top is an operator with higher or equal precedence (consider associativity), pop to output; then push op.
3. After scan, pop remaining operators to output; the result is postfix.

Steps: Infix to Prefix (Reverse + Shunting-yard + Reverse)

1. Reverse the infix string and swap ‘(‘ with ‘)’.
2. Run a shunting-yard-like pass but pop while strictly greater precedence on the stack to honor right-to-left evaluation after reversal.
3. Reverse the produced sequence; the result is prefix.

Steps: Prefix ↔ Postfix (Stack-based)

1. Prefix to Postfix: scan right-to-left; push operands; on operator, pop two items a, b, form abOp; push back; end with single postfix string.
2. Postfix to Prefix: scan left-to-right; push operands; on operator, pop b, a, form Opab; push back; end with single prefix string.

Java Implementation: Convert and Evaluate All Three Notations

The following Java utility demonstrates production-ready, stack-based algorithms that convert infix to postfix and prefix, and evaluate postfix and prefix numerically. Tokens are single-character operands for simplicity (easily extendable to multi-digit by tokenizing), and operators include +, -, *, /, and ^ with standard precedence and left associativity except for ^ which is typically right-associative. The code uses Deque as a stack for clarity and adheres to O(n) time for each conversion/evaluation. Infix→prefix is implemented with the reverse-swap-parentheses technique to reuse the shunting-yard core. After the code, a step-by-step explanation describes exactly how each method works, where and why elements are pushed or popped, and the subtle associativity difference needed to get correct prefix output. You can drop this class into a DSA playground, add tokenization for numbers/variables, and use it to validate conversions with unit tests or to support an expression module in a basic interpreter or calculator UI.

import java.util.*;
public class ExpressionUtils {

    private static boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
    }

    private static int precedence(char c) {
        switch (c) {
            case '^': return 3;
            case '*':
            case '/': return 2;
            case '+':
            case '-': return 1;
            default: return 0;
        }
    }

    private static boolean isRightAssociative(char c) {
        return c == '^';
    }

    // Infix to Postfix (Shunting-yard)
    public static String infixToPostfix(String expr) {
        Deque<Character> stack = new ArrayDeque<>();
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < expr.length(); i++) {
            char ch = expr.charAt(i);
            if (Character.isWhitespace(ch)) continue;

            if (Character.isLetterOrDigit(ch)) {
                out.append(ch);
            } else if (ch == '(') {
                stack.push(ch);
            } else if (ch == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    out.append(stack.pop());
                }
                if (!stack.isEmpty() && stack.peek() == '(') stack.pop();
            } else if (isOperator(ch)) {
                while (!stack.isEmpty() && isOperator(stack.peek())) {
                    char top = stack.peek();
                    boolean higher = precedence(top) > precedence(ch);
                    boolean equalAndLeft = precedence(top) == precedence(ch) && !isRightAssociative(ch);
                    if (higher || equalAndLeft) {
                        out.append(stack.pop());
                    } else break;
                }
                stack.push(ch);
            }
        }
        while (!stack.isEmpty()) {
            out.append(stack.pop());
        }
        return out.toString();
    }

    // Infix to Prefix (Reverse + Shunting-yard + Reverse)
    public static String infixToPrefix(String expr) {
        StringBuilder rev = new StringBuilder();
        for (int i = expr.length() - 1; i >= 0; i--) {
            char ch = expr.charAt(i);
            if (ch == '(') rev.append(')');
            else if (ch == ')') rev.append('(');
            else rev.append(ch);
        }
        // Run a modified shunting-yard on the reversed string
        Deque<Character> stack = new ArrayDeque<>();
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < rev.length(); i++) {
            char ch = rev.charAt(i);
            if (Character.isWhitespace(ch)) continue;

            if (Character.isLetterOrDigit(ch)) {
                out.append(ch);
            } else if (ch == '(') {
                stack.push(ch);
            } else if (ch == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') out.append(stack.pop());
                if (!stack.isEmpty() && stack.peek() == '(') stack.pop();
            } else if (isOperator(ch)) {
                // For prefix (on reversed input), pop only strictly higher precedence
                while (!stack.isEmpty() && isOperator(stack.peek())) {
                    char top = stack.peek();
                    boolean strictlyHigher = precedence(top) > precedence(ch) ||
                                             (precedence(top) == precedence(ch) && isRightAssociative(top) && isRightAssociative(ch));
                    if (strictlyHigher) out.append(stack.pop());
                    else break;
                }
                stack.push(ch);
            }
        }
        while (!stack.isEmpty()) out.append(stack.pop());
        return out.reverse().toString();
    }

    // Evaluate Postfix (operands are single digits or letters mapped via vars)
    public static int evaluatePostfix(String postfix, Map<Character, Integer> vars) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < postfix.length(); i++) {
            char ch = postfix.charAt(i);
            if (Character.isWhitespace(ch)) continue;

            if (Character.isDigit(ch)) {
                stack.push(ch - '0');
            } else if (Character.isLetter(ch)) {
                if (!vars.containsKey(ch)) throw new IllegalArgumentException("Missing value for " + ch);
                stack.push(vars.get(ch));
            } else if (isOperator(ch)) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(apply(a, b, ch));
            } else {
                throw new IllegalArgumentException("Unexpected token: " + ch);
            }
        }
        return stack.pop();
    }

    // Evaluate Prefix (scan right-to-left)
    public static int evaluatePrefix(String prefix, Map<Character, Integer> vars) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = prefix.length() - 1; i >= 0; i--) {
            char ch = prefix.charAt(i);
            if (Character.isWhitespace(ch)) continue;

            if (Character.isDigit(ch)) {
                stack.push(ch - '0');
            } else if (Character.isLetter(ch)) {
                if (!vars.containsKey(ch)) throw new IllegalArgumentException("Missing value for " + ch);
                stack.push(vars.get(ch));
            } else if (isOperator(ch)) {
                int a = stack.pop();
                int b = stack.pop();
                stack.push(apply(a, b, ch));
            } else {
                throw new IllegalArgumentException("Unexpected token: " + ch);
            }
        }
        return stack.pop();
    }

    private static int apply(int a, int b, char op) {
        switch (op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            case '/': return a / b; // assume exact division for brevity
            case '^': return (int)Math.pow(a, b);
            default: throw new IllegalArgumentException("Bad op " + op);
        }
    }

    // Demo
    public static void main(String[] args) {
        String infix = "(A+B)*(C-D)";
        String post = infixToPostfix(infix);
        String pre = infixToPrefix(infix);
        System.out.println("Infix   : " + infix);
        System.out.println("Postfix : " + post);
        System.out.println("Prefix  : " + pre);

        Map<Character, Integer> vars = new HashMap<>();
        vars.put('A', 3); vars.put('B', 4); vars.put('C', 9); vars.put('D', 5);
        System.out.println("Evaluate Postfix: " + evaluatePostfix(post, vars));
        System.out.println("Evaluate Prefix : " + evaluatePrefix(pre, vars));
    }
}

Step-by-step Explanation of the Java Program

• precedence, isRightAssociative: Encode operator hierarchy: ^ highest and right-associative; * and / medium; + and – lowest. This drives when to pop from the operator stack.
• infixToPostfix: Implements shunting-yard: appends operands immediately; pushes ‘(‘; on ‘)’, drains until ‘(‘; on operator op, pops while the stack top is an operator with higher precedence, or equal precedence for left-associative ops, ensuring emitted order respects binding; finally flushes remaining operators. Output is the postfix string.
• infixToPrefix: Reverses the infix and swaps parentheses; runs a modified yard where an operator on the stack must have strictly higher precedence before popping (and a tie-break for right-associative ^). Reverses the final output to get correct prefix. This trick reuses the core logic safely.
• evaluatePostfix: Scans left-to-right; pushes digits directly; for letters, pulls values from a map; upon operator, pops right operand then left operand, applies, and pushes result; the last value is the result.
• evaluatePrefix: Mirrors postfix but scans right-to-left; on operator, pops left then right sub-results (a then b to preserve order), applies, pushes; ends with the result.
• Error-handling: Minimal checks ensure unexpected characters or missing variable bindings are caught early.
• Extensibility: Replace single-character scanning with tokenization to support multi-digit numbers, unary minus, functions, and additional operators without changing the algorithmic backbone.

Time and Space Complexity

For expression processing with n tokens, the standard stack-based algorithms operate in strictly linear time because each token is pushed and popped a constant number of times, and all comparisons are O(1). The shunting-yard for infix→postfix and the reversed variant for infix→prefix both walk the token stream once, with stack operations proportional to the number of operators and parentheses. Evaluation of postfix and prefix also reads the input once, creating at most one intermediate value per operator. Space complexity is linear in the worst case because the operator stack (for conversion) or operand stack (for evaluation) can grow to O(n) under adversarial constructs such as many consecutive operands followed by operators (for postfix) or deeply nested parentheses/operators (for conversion). If you convert via an expression tree, building the tree requires O(n) time and space and then linear traversals emit prefix or postfix in O(n). The table below lists typical bounds and the key constant-time actions; note that extending to multi-character tokens, function calls, or unary operators preserves complexity under the same stack or AST approach.

Advantages, Disadvantages, and Applications

Each notation optimizes a different axis: infix is ergonomically ideal for humans, but it burdens machines with parsing, precedence, associativity, and parentheses tracking; prefix and postfix encode binding in position so machines can process them in a single pass with a simple stack or recursive descent, a property that translates well to bytecode, interpreters, and compilers. From a systems perspective, postfix dovetails with stack machine architectures and register minimization, while prefix aligns elegantly with function-application views in formal logic and abstract syntax. In typical DSA curricula, you will convert infix to postfix and then evaluate postfix with a stack because the combination is both conceptually clear and performant. In production, parsers usually build an AST from infix tokens (using precedence-climbing or Pratt parsing) and then emit either notation as an intermediate representation for optimization and code generation, demonstrating that notations are algorithms’ interfaces rather than ends in themselves.

Advantages

• Infix: Human-readable; mirrors textbook arithmetic; natural for most programming languages and IDE tooling.
• Postfix: No parentheses; unambiguous; single-pass stack evaluation; ideal for calculators, bytecode, and VM execution.
• Prefix: No parentheses; unambiguous; maps to recursive parsing and function-application semantics; useful in logic systems.

Disadvantages

• Infix: Requires precedence/associativity handling; parentheses overhead; harder to evaluate directly and correctly.
• Postfix: Less intuitive for newcomers; requires a stack at runtime; reading by humans can be slower.
• Prefix: Also less intuitive; right-to-left or recursive evaluation can be unfamiliar; debugging by inspection is harder.

Applications

• Compilers/Interpreters: Parse infix to AST, then emit prefix/postfix IR for optimization and codegen.
• Calculators/VMs: Postfix evaluation for stack machines; minimal state and predictable performance.
• Formal Logic/Proof Assistants: Prefix tightly models n-ary operators as function application.
• Education/Interviews: Classic DSA problems: shunting-yard, expression-tree traversals, stack evaluation.

Worked Examples with Step-by-step Conversions

Consider the compound infix expression (A + B) * C – (D – E) * (F + G). To derive postfix, apply the shunting-yard steps: emit A, B, then + when closing the first parentheses; push * and C appropriately to get AB+ C*; handle (D – E) as DE- and (F + G) as FG+; then emit * for their product and finally – combining the two big sub-results, yielding AB+ C* DE- FG+ * -. For the prefix form, reverse the infix and swap parentheses, run the modified yard, and reverse back to get – * + A B C * – D E + F G. Alternatively, build an expression tree: the root is -, with left child * whose left is + (A,B) and right is C; the right child is * whose left is – (D,E) and right is + (F,G). A pre-order traversal prints the prefix, and a post-order traversal prints the postfix. Throughout, note that operands keep their relative order (A precedes B globally across all notations), parentheses disappear in prefix/postfix, and operator positions alone encode precedence. If you substitute values (A=3,B=4,C=5,D=9,E=5,F=2,G=1), evaluating postfix with a stack or prefix with right-to-left scanning yields the same numeric result without ever consulting a precedence table at runtime, illustrating the computational advantage of Polish notations.

• Infix: (A + B) * C – (D – E) * (F + G)
• Postfix (steps):
  1. (A + B) → AB+
  2. AB+ * C → AB+C*
  3. (D – E) → DE-; (F + G) → FG+; product → DE-FG+*
  4. Final subtraction → AB+C*DE-FG+*-
• Prefix: – * + A B C * – D E + F G

Analogies To Build Intuition

If infix, prefix, and postfix feel abstract, anchor them to everyday mental models. Think of infix as typical spoken math: “add B to A, then multiply by C,” which relies on shared rules like “do multiplication before addition” or clarifying parentheses—great for humans, but you must know the grammar. Visualize postfix as a conveyor belt with a box stacker: items (operands) come down the belt; you stack them; when a label (operator) arrives, you pop the necessary boxes, combine them, and put the result back on the stack; you never look ahead and never wonder about parentheses. Imagine prefix as function calls: + A B is exactly like calling plus(A, B), and * + A B C is multiply(plus(A,B),C); you see what operation is coming before you read the data, which helps recursive parsers. In all three analogies, the underlying “work” is identical, but the cognitive burden shifts: infix offloads structure to punctuation and priority rules, postfix/prefix encode it in position. This framing explains why programming languages expose infix to users for legibility yet internally pivot to postfix/prefix-like forms where a simple stack or recursion suffices. When preparing for interviews, keep the conveyor belt (postfix) and function-call (prefix) analogies in mind—they make it trivial to reason about when to push, pop, and apply operators as you trace examples or dry-run code by hand.

FAQs

Engineers and students often share recurring doubts as they bridge human-friendly notation and machine-friendly forms. First, all three notations are semantically equivalent when operator arity and operand order are preserved, so conversions never change the computed value; they only change where operators appear. Second, why convert at all? Because parsing infix directly requires operator-precedence grammars or parser generators, whereas prefix/postfix can be evaluated with a tiny stack or a few lines of recursion in O(n). Third, are parentheses needed in prefix/postfix? No—operator position encodes binding, so parentheses vanish; this is a feature that reduces ambiguity and runtime checks. Fourth, which notation do calculators and compilers use? Many stack calculators and bytecode interpreters use postfix internally; compilers commonly parse infix to an AST and then emit postfix/prefix-like IR. Fifth, how do unary operators fit? With tokenization, treat unary minus as a separate operator with high precedence and appropriate associativity; the same stack rules apply. Sixth, what if tokens are multi-digit or variable names? Tokenize first (split on spaces or use a lexer) and process tokens instead of characters; complexity remains O(n). Finally, what’s best for learning? Practice infix→postfix with a stack, evaluate postfix by hand, then mirror to prefix; build an expression tree and verify that pre-order prints prefix and post-order prints postfix—this unifies all views elegantly.

• Do prefix/postfix need precedence tables? No. Placement encodes binding; a single pass with a stack or recursion suffices.
• Is operand order preserved? Yes. Across notations, operands keep their mutual order; only operators move.
• Can I evaluate infix directly? Yes, with two stacks (operands/operators) or by building an AST; most courses prefer convert-then-evaluate.
• Where are they used? Infix for language syntax; postfix/prefix in compilers, VMs, calculators, and logic tools.