Postfix Expression: Stack Evaluation, C Code & Examples

A postfix expression is an arithmetic or logical expression where every operator appears after its operands. Evaluating it matters because compilers, calculators, query engines, and virtual machines can process it without parentheses or precedence checks. After reading, you can trace, validate, and implement postfix evaluation using a stack.

Postfix notation is part of expression processing, which also includes infix and prefix forms.

You will be able to solve postfix evaluation examples by hand, write postfix evaluation in C, handle multi-digit operands, detect malformed inputs, and explain the stack algorithm confidently in GATE-style and placement interviews.

---

Who This Guide Is For

This guide is specifically designed for:

---

Core Concepts

Evaluation of postfix expression is built around one idea: scan tokens from left to right, push operands, and apply operators to the latest available operands. The stack removes the need for parentheses because the order of operations is already encoded in the expression. The topic connects directly to stack ADT operations, compiler design, expression trees, bytecode execution, and calculator implementation.

1.Postfix Notation

Postfix notation, also called Reverse Polish Notation, places the operator after its operands. The infix expression 3 + 4 becomes 3 4 +, and (3 + 4) * 5 becomes 3 4 + 5 *. The mental model is a pile of pending values: operands are placed on the pile, and an operator consumes the top required values.

A familiar example is a shopkeeper calculator where 100 18 + can represent adding 18 percent GST after entering the base price. An industry-specific example is a healthcare billing engine using consultation lab + discount -, where variable names are resolved from a patient invoice before evaluation. In both cases, postfix removes ambiguity because the sequence itself tells the evaluator what to compute first.

For GATE and interviews, the standard first question is: evaluate a given postfix expression step by step. The expected answer must show the stack after each token, not only the final result.

Code Example

2.Stack Algorithm

Postfix evaluation using stack follows a deterministic algorithm. Read one token at a time. If the token is an operand, push it. If the token is an operator, pop the required operands, compute the result, and push that result back. After the final token, the stack must contain exactly one value.

A familiar example is splitting a restaurant bill using 1200 3 / 50 +, meaning divide ₹1200 among three friends and add ₹50 tip per person. A production example is a SaaS subscription calculator using base users rate * + tax +, where each variable represents a field from the pricing database. The stack algorithm works for both because it does not care whether tokens are hardcoded numbers or resolved business values.

When an operator is found, always pop the right operand first and the left operand second. For subtraction and division, reversing this order changes the answer.

Code Example

3.Token Handling

Token handling decides whether your evaluator works only for textbook expressions or for real input. A character-by-character approach can evaluate 23+ as 2 3 +, but it fails for 23 7 + because 23 is a single operand, not two separate digits. Intermediate and advanced learners should prefer space-delimited tokens unless the input grammar is explicitly single-character.

A familiar example is a mobile recharge calculation such as 299 18.0 +, where the decimal token must remain intact. An industry-specific example is an ed-tech analytics formula such as watch_minutes quiz_score + 2 /, where identifiers must be resolved before arithmetic. Good token handling supports integers, decimals, negative numbers, and variables without changing the core stack logic.

Do not evaluate multi-digit postfix expressions by reading one character at a time unless the problem explicitly says every operand is a single digit. This is a common source of wrong answers in coding tests.

Code Example

4.Operand Order

Operand order is the most tested detail in evaluation of postfix expression. When a binary operator appears, the first popped value is the right operand, and the second popped value is the left operand. This distinction does not affect addition and multiplication, but it changes subtraction, division, exponentiation, and comparisons.

A familiar example is 20 5 -, which means 20 - 5, not 5 - 20. A banking example is a loan calculation rule such as available_balance hold_amount -, where reversing operands would produce a negative or inflated value and could block a valid transaction incorrectly. For interviews, state the pop order explicitly before writing code.

If the expression contains - or /, examiners often check whether you preserve operand order. For 8 2 /, the answer is 4, not 0.25.

Code Example

5.Unary Operators

Unary operators consume one operand instead of two. Common examples include negation, absolute value, square root, and logical NOT. A robust postfix evaluator should know the arity of every operator; otherwise, it may incorrectly pop two operands for an operator that needs only one.

A familiar example is temperature adjustment with -5 abs, which returns 5. An industry-specific example is a logistics dashboard using delay_minutes neg to convert a delay into a penalty adjustment. Unary support becomes essential in compilers and expression engines because real formulas rarely use only binary arithmetic.

Unary minus and binary subtraction should be represented differently in postfix evaluators. For example, use neg for unary negation and - for binary subtraction.

Code Example

6.Functions and Arity

Function-style postfix extends the same stack idea to operators with named behaviour and known arity. For example, 2 3 pow can represent 2^3, and 10 20 max returns 20. The evaluator must know how many operands each function consumes.

A familiar example is calculating the larger of two discount offers with bank_offer coupon_offer max. A fintech risk engine may use income debt ratio where ratio consumes two values and returns a derived score. Advanced expression evaluators often store operators in a registry so new functions can be added without rewriting the parsing loop.

Every postfix operator must have a known arity. Binary arithmetic uses arity 2, unary negation uses arity 1, and custom functions must declare how many operands they consume.

Code Example

7.Error Validation

Invalid postfix expressions usually fail in four ways: an operator appears before enough operands, unknown tokens appear, division by zero occurs, or extra operands remain after scanning all tokens. Production-grade evaluators must detect these cases rather than relying on stack underflow errors or returning misleading results.

A familiar example is 5 +, which is invalid because the plus operator has only one operand. An industry-specific example is an insurance premium engine where age risk + base leaves an extra unresolved operand, meaning the rule is incomplete. Validation is not optional when formulas come from users, databases, or configuration files.

A valid postfix expression must end with exactly one value on the stack. Zero values means the expression was incomplete; more than one value means some operands were never combined.

Code Example

8.C Implementation

Postfix evaluation in C is commonly tested because it checks both stack logic and low-level implementation discipline. You usually create an array-based stack, maintain a top index, scan tokens, push operands, and pop operands for operators. For serious code, prefer token-based parsing with strtok or a manual scanner so multi-digit values work correctly.

A familiar example is a command-line calculator used in a DSA lab. An industry-specific example is an embedded billing terminal that evaluates configured arithmetic rules without a heavy expression parser. C code also makes overflow, division by zero, and stack capacity explicit, which is why interviewers like this implementation.

For postfix evaluation in C, mention the stack array, top pointer, push and pop operations, and the final condition that top must be zero after successful evaluation.

Code Example

The complete postfix evaluation rule is: push operands, pop operands only when an operator appears, apply left operator right, push the result, and accept only if one final value remains.

---

Worked Examples

Postfix evaluation examples are best solved by maintaining a stack table. Write the token, action, and stack state after every step. This method prevents mental shortcuts from breaking operand order.

Arithmetic Trace

Evaluate 5 6 2 + * 12 4 / -. This represents 5 * (6 + 2) - (12 / 4). The stack states are: push 5, push 6, push 2, apply + to get 8, apply * to get 40, push 12, push 4, apply / to get 3, then apply - to get 37.

Business Formula Trace

Consider an e-commerce margin formula selling_price platform_fee - packaging_cost -. If selling_price = 850, platform_fee = 120, and packaging_cost = 30, the result is 700. The same stack algorithm works because variable names are resolved to values before computation.

---

Complexity Analysis

Postfix evaluation runs in linear time because each token is processed once. If the expression has n tokens, the time complexity is O(n). The auxiliary space is O(n) in the worst case, when many operands appear before operators.

A familiar example is 1 2 3 4 + + +, where the stack grows before shrinking. An industry-specific example is a reporting engine evaluating a long KPI expression with dozens of fields before aggregation. Even then, stack operations remain constant time, so the total runtime grows predictably with the number of tokens.

The standard complexity answer is: evaluation of postfix expression takes O(n) time and O(n) auxiliary space in the worst case, where n is the number of tokens.

Code Example

---

Learning Path

Use this path to move from textbook postfix evaluation to interview-ready and production-aware implementation. Practise by tracing first, then coding, then validating edge cases.

---

Frequently Asked Questions

What is postfix expression evaluation?

Postfix expression evaluation is the process of computing an expression where operators appear after operands, such as 2 3 +. It is usually done with a stack because operands can be stored until an operator arrives. This technique is used in compilers, calculators, interpreters, and DSA interview questions.

How does postfix evaluation using stack work?

Scan the expression from left to right. Push operands onto the stack; when an operator appears, pop the required operands, apply the operator, and push the result. A valid expression ends with exactly one value on the stack.

What is the difference between infix and postfix?

Infix places operators between operands, such as A + B. Postfix places operators after operands, such as A B +. Infix needs precedence and parentheses during parsing, while postfix can be evaluated directly with a stack.

Why is operand order important?

For a binary operator, the first popped value is the right operand and the second popped value is the left operand. This matters for subtraction, division, exponentiation, and comparisons. For example, 9 3 - means 9 - 3, not 3 - 9.

How do you handle multi-digit operands?

Use space-separated tokens instead of reading characters one by one. The expression 12 30 + should be tokenised as 12, 30, and +. In C, functions such as strtok and strtod can help parse these tokens.

What are common mistakes in postfix evaluation?

The most common mistakes are reversing operand order, ignoring stack underflow, treating multi-digit numbers as separate digits, and not checking the final stack size. Another frequent issue is forgetting to handle division by zero. Good evaluators validate every operator before applying it.

What is the time complexity?

The time complexity is O(n), where n is the number of tokens. Each token is processed once, and each stack operation takes constant time. The worst-case auxiliary space is O(n).

Is postfix evaluation asked in interviews?

Yes, postfix expression questions are common in DSA interviews because they test stack usage, edge-case thinking, and clean implementation. Interviewers often ask candidates to evaluate a sample expression, write code, and explain error handling. C, Java, Python, and JavaScript implementations are all acceptable if the logic is correct.

---

Interview Preparation

Postfix questions appear in interviews because they are compact but reveal whether a candidate truly understands stacks. Approach them by stating the algorithm, clarifying token format, preserving operand order, and validating the final stack state.

Conceptual Questions

• Why is stack the preferred data structure for postfix evaluation? A stack naturally stores operands until the next operator needs them. Since the latest operands must be used first, LIFO behaviour matches postfix evaluation exactly.
• Why does postfix notation not need parentheses? The operator position already fixes the order of computation. For example, A B + C * clearly means compute A + B first, then multiply by C.
• What should remain on the stack after evaluation? Exactly one value should remain. If the stack has more than one value, some operands were unused; if it becomes empty too early, the expression lacks operands.
• How are unary operators different from binary operators? Unary operators consume one operand, while binary operators consume two. A correct evaluator stores or checks operator arity before popping from the stack.

Applied / Problem-Solving Questions

• Evaluate 6 2 / 3 4 + *. First compute 6 / 2 = 3, then 3 + 4 = 7, then 3 * 7 = 21. The final answer is 21.
• Write the core algorithm for postfix evaluation in C. Use an array as a stack, scan tokens, push numeric operands, pop right then left for operators, push the computed result, and ensure the final top index is zero. Also handle invalid tokens and division by zero.
• How would you support variables in postfix evaluation? Maintain a symbol table such as a map or dictionary. When a token is not an operator, resolve it from the symbol table and push its numeric value.
• How would you detect malformed postfix expressions? Before applying a binary operator, check that at least two operands are available. After scanning all tokens, verify that exactly one value remains on the stack.

The most tested question is: evaluate a postfix expression and show stack contents after every token. The standard answer must include correct pop order: right operand first, left operand second.

---

Key Takeaways

Postfix expression evaluation uses a stack, scans tokens left to right, pushes operands, applies operators when found, and accepts the expression only when one final value remains. Multi-digit numbers, decimals, variables, unary operators, and functions require tokenisation and operator arity handling. Robust implementations must detect missing operands, extra operands, unknown tokens, and division by zero.

For GATE and interviews, the most tested points are stack tracing, O(n) time complexity, O(n) worst-case space, correct operand order for - and /, and postfix evaluation in C using push and pop operations.

The natural next step is How to Evaluate Postfix Expression, which reinforces the same concept with additional reference material and helps you revise before timed practice.