Postfix Expression Evaluation Using Stack in Data Structure
Learn Postfix Evaluation with simple explanations, LIFO Stack diagrams, Push and Pop operations, algorithms, step-by-step dry runs, C programming, memory tricks and exam questions.
Suppose your teacher writes the following expression on the board:
At first, it may look confusing. The numbers and operators are not arranged like a normal mathematical expression.
You may wonder where the brackets are, which operation should happen first, and how to calculate the final answer.
This is called a Postfix Expression. It becomes easy when we use a Stack and follow a few simple rules.
If you want to revise the basic LIFO principle and Stack operations, read Stack in Data Structure: Operations, Implementation and Applications .
What is Postfix Expression Evaluation?

Postfix Expression Evaluation is the process of finding the numerical value of an expression written in Postfix notation.
In Postfix notation, a binary operator is written after its two operands.
This represents the normal Infix expression A + B.
Understand With a Simple Example
5 + 3
Operator is placed between operands.
5 3 +
Operator is placed after the operands.
8
Both expressions produce the same answer.
Postfix notation is also known as Reverse Polish Notation (RPN).
A useful property of an unambiguous Postfix expression is that we do not need parentheses to specify the order of binary operations.
Postfix Expression Diagram
POST means AFTER. In Postfix, the operator is written after its operands.
How Does Postfix Evaluation Using Stack Work?
Postfix Evaluation uses a Stack to store numbers temporarily.
When an operator is found, the required operands are taken from the Stack.
Operand → Push into Stack.
Operator → Pop two operands, calculate, then Push the result.
Step-by-Step Working
Initially, there are no values inside the Stack.
Process the expression one token at a time.
If the current token is a number, insert it into the Stack.
Pop the first value as RIGHT and the second value as LEFT.
Perform LEFT operator RIGHT and Push the result into the Stack.
After processing all tokens, a valid expression must leave exactly one value.
Visualise the Stack
Consider the following Postfix expression:
First, 5 is pushed onto the Stack. Then 3 is pushed above 5.
When + is encountered, both numbers are removed, added, and 8 is pushed into the Stack.
Algorithm for Postfix Expression Evaluation Using Stack
An algorithm is a step-by-step procedure used to solve a particular problem.
The Postfix Evaluation algorithm uses Push and Pop operations to calculate the expression.
Postfix Evaluation Algorithm
START
CREATE EMPTY STACK
SCAN EXPRESSION LEFT TO RIGHT
FOR EACH TOKEN
IF TOKEN IS OPERAND
PUSH TOKEN INTO STACK
ELSE IF TOKEN IS BINARY OPERATOR
IF STACK HAS FEWER THAN 2 VALUES
RETURN ERROR
END IF
RIGHT = POP()
LEFT = POP()
RESULT = LEFT OPERATOR RIGHT
PUSH RESULT
END IF
END FOR
IF STACK HAS EXACTLY ONE VALUE
RETURN POP()
ELSE
RETURN INVALID EXPRESSION
END IF
STOP
Important Points About the Algorithm
Scanning Direction
Read the Postfix expression from left to right.
Operand Handling
Store every operand in the Stack until required.
Operator Handling
Pop two values, perform the operation and Push the result.
Final Condition
Exactly one value must remain in the Stack.
S-P-C-P
S = Scan expression
P = Push operands
C = Calculate operators
P = Push result
Postfix Expression Evaluation: Step-by-Step Dry Run
A dry run means solving an algorithm manually to understand what happens at each step.
This type of question is important for university examinations because it checks both Stack operations and mathematical logic.
Solved Example 1: Evaluate the Expression
We will process every token and observe the Stack after each operation.
Complete Dry Run Table
| Step | Token | Operation | Stack (Bottom → Top) |
|---|---|---|---|
| 1 | 5 | Push 5 | 5 |
| 2 | 6 | Push 6 | 5, 6 |
| 3 | 2 | Push 2 | 5, 6, 2 |
| 4 | + | 6 + 2 = 8 | 5, 8 |
| 5 | * | 5 × 8 = 40 | 40 |
| 6 | 12 | Push 12 | 40, 12 |
| 7 | 4 | Push 4 | 40, 12, 4 |
| 8 | / | 12 / 4 = 3 | 40, 3 |
| 9 | - | 40 - 3 = 37 | 37 |
Explanation of Each Calculation
These are operands, so store all three in the Stack.
Pop 2 and 6. Calculate 6 + 2 = 8. Push 8.
Pop 8 and 5. Calculate 5 × 8 = 40. Push 40.
The Stack contains 40, 12 and 4.
Pop 4 and 12. Calculate 12 / 4 = 3. Push 3.
Pop 3 and 40. Calculate 40 - 3 = 37. Push 37.
Since only one value remains in the Stack, the expression has been successfully evaluated.
Final Stack Diagram
Always show four columns in Postfix dry-run questions: Token, Operation, Stack Content and Final Result.
Clearly mention whether the Stack is written from bottom to top or top to bottom.
More Solved Postfix Evaluation Examples
Let us solve a few different types of expressions so that the Stack operations become easier to understand.
Example 2: Multiplication and Addition
Follow these steps:
Push 12, 3 and 4.
* appears. Calculate 3 × 4 = 12.
+ appears. Calculate 12 + 12 = 24.
Example 3: Division and Subtraction
| Token | Action | Stack |
|---|---|---|
| 20 | Push | 20 |
| 5 | Push | 20, 5 |
| - | 20 - 5 = 15 | 15 |
| 3 | Push | 15, 3 |
| / | 15 / 3 = 5 | 5 |
Example 4: Exponentiation
Here, ^ represents exponentiation in the mathematical expression.
Push 3 and 2.
Process ^. Calculate 3² = 9.
Push 4.
Process +. Calculate 9 + 4 = 13.
Example 5: Negative Number
In this expression, -5 is a single negative-number token, not the binary subtraction operator.
First, -5 × 2 = -10. Then -10 + 6 = -4.
Why is Operand Order Important in Postfix Evaluation?
This is one of the most important concepts in Postfix Evaluation.
Students sometimes reverse the operands after performing Pop. This can produce incorrect answers in subtraction and division.
First Pop = Right Operand
Second Pop = Left Operand
Subtraction Example
Push 10, then Push 3. The TOP contains 3.
10 - 3 = 7
LEFT = 10
RIGHT = 3
3 - 10 = -7
This reverses the operand positions.
Division Example
First Pop returns 4, so RIGHT = 4.
Second Pop returns 20, so LEFT = 20.
Operand Order Memory Trick
R-L Rule: Right first, Left second.
This rule is especially important for subtraction, division and exponentiation.
Postfix Expression Evaluation Using Stack in C
Now let us understand how to implement the Postfix Evaluation algorithm using C programming.
We will use an array-based Stack to store numerical operands.
The program reads a space-separated Postfix expression and produces the final result.
Features of the C Program
Multiple Operators
Supports +, -, *, / and ^.
Different Number Types
Supports multi-digit values, negative values and decimals.
Stack Validation
Checks insufficient operands, capacity and final Stack size.
Error Handling
Checks invalid tokens, division by zero and non-finite results.
Complete C Program
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <math.h>
#define STACK_CAPACITY 128
#define INPUT_SIZE 1024
int isOperator(const char *token) {
return strlen(token) == 1 &&
strchr("+-*/^", token[0]) != NULL;
}
int evaluatePostfix(char *expression, double *answer) {
double stack[STACK_CAPACITY];
int top = -1;
char *token = strtok(expression, " \t\r\n");
if (token == NULL) {
puts("Error: Empty expression");
return 0;
}
while (token != NULL) {
if (isOperator(token)) {
if (top < 1) {
puts("Error: Not enough operands");
return 0;
}
double right = stack[top--];
double left = stack[top--];
double result;
switch (token[0]) {
case '+':
result = left + right;
break;
case '-':
result = left - right;
break;
case '*':
result = left * right;
break;
case '/':
if (right == 0) {
puts("Error: Division by zero");
return 0;
}
result = left / right;
break;
default:
result = pow(left, right);
break;
}
if (!isfinite(result)) {
puts("Error: Result is not a finite number");
return 0;
}
stack[++top] = result;
} else {
char *end;
errno = 0;
double value = strtod(token, &end);
if (end == token || *end != '\0' ||
errno == ERANGE || !isfinite(value)) {
puts("Error: Invalid number or symbol");
return 0;
}
if (top == STACK_CAPACITY - 1) {
puts("Error: Stack overflow");
return 0;
}
stack[++top] = value;
}
token = strtok(NULL, " \t\r\n");
}
if (top != 0) {
puts("Error: Invalid postfix expression");
return 0;
}
*answer = stack[top];
return 1;
}
int main(void) {
char expression[INPUT_SIZE];
double answer;
printf("Enter postfix (use spaces): ");
if (fgets(expression, sizeof(expression), stdin) == NULL)
return 1;
if (evaluatePostfix(expression, &answer))
printf("Result = %.10g\n", answer);
return 0;
}
Example Input
5 6 2 + * 12 4 / -
Output
Enter postfix (use spaces): 5 6 2 + * 12 4 / -
Result = 37
How to Run the Program?
Save the program in VS Code
with the filename
postfix_evaluation.c.
If GCC is installed, open the VS Code terminal and compile it using:
gcc postfix_evaluation.c -o postfix_evaluation -lm
On Windows, run:
.\postfix_evaluation.exe
Enter the Postfix expression with spaces between tokens.
-lm option links
the mathematical library needed
by pow() on GCC
toolchains that require it.
In this program, ^ represents
exponentiation through pow().
In ordinary C expressions, ^
is the bitwise XOR operator.
Explanation of Important Functions
Checks whether a token is one of the supported binary operators.
Separates the entered expression into tokens using spaces and other whitespace.
Converts a numeric token into a double value.
Uses the Stack to process operands and perform mathematical operations.
Reads the expression, calls the evaluation function and prints the result.
More Inputs to Practise
| Postfix Input | Expected Result |
|---|---|
| 8 2 / 3 + | 7 |
| 12 3 4 * + | 24 |
| 20 5 - 3 / | 5 |
| 3 2 ^ 4 + | 13 |
| -5 2 * 6 + | -4 |
| 5 2 / | 2.5 |
This classroom implementation uses a fixed Stack capacity, a fixed input buffer and double-precision arithmetic.
It supports space-separated numeric expressions only. Variables, unary operators as separate tokens, complex numbers and very large expressions are not supported. Extremely large or small values may cause floating-point limitations.
Errors and Common Mistakes in Postfix Evaluation
A Postfix Evaluation program must check whether the expression is valid before returning an answer.
1. Insufficient Operands
The + operator needs two operands, but only one is available.
2. Extra Operands
Both operands remain without an operator. The final Stack has two values.
3. Division by Zero
The denominator becomes zero, so evaluation must report an error.
4. Invalid Token
A cannot be evaluated numerically unless a value has been supplied.
5. Reversed Operand Order
The correct result is 7, not -7.
6. Incorrect Scanning
Standard Stack-based Postfix Evaluation scans from left to right.
When is a Postfix Expression Valid?
For a binary-operator Postfix expression, every operator must have two operands available when it is processed.
After the complete expression has been processed, exactly one Stack value must remain.
"Two for Operator, One for Answer."
Every binary operator needs two operands. A valid completed evaluation leaves one final result.
Time and Space Complexity of Postfix Evaluation
Complexity analysis tells us how the required time and memory grow with the number of expression tokens.
Time Complexity
In standard Postfix Evaluation, every token is scanned once.
Push and Pop require O(1) time in an array-based Stack when sufficient capacity exists.
Space Complexity
A Stack temporarily stores operands and intermediate results.
In the worst case, Stack storage grows linearly with the number of tokens.
| Operation | Time Complexity |
|---|---|
| Push | O(1) |
| Pop | O(1) |
| Peek | O(1) |
| Process One Operator | O(1) for basic arithmetic |
| Evaluate n Tokens | O(n) |
The O(n) evaluation bound assumes constant-time basic operations and bounded-size numeric tokens.
The C example uses a fixed array capacity of 128, while the abstract algorithm may require up to O(n) Stack storage. Mathematical library operations such as pow() have their own implementation costs.
Applications of Postfix Expression Evaluation
Postfix Evaluation is useful wherever expressions need to be processed using an explicit evaluation order.
Stack-Based Calculators
Postfix notation is used in Reverse Polish Notation calculators where values are stored and combined through a Stack.
Compiler and Interpreter Concepts
Stack-based evaluation helps explain how programming expressions can be converted into executable operations.
Expression Processing
Postfix notation provides an ordered representation that does not require parentheses for unambiguous binary expressions.
Educational Algorithms
Postfix Evaluation is a practical way to understand Stack operations, algorithms, expression parsing and data processing.
Difference Between Postfix Evaluation and Infix Evaluation
Both approaches calculate expressions, but the processing methods are different.
| Feature | Infix | Postfix |
|---|---|---|
| Operator Position | Between operands | After operands |
| Example | 5 + 3 | 5 3 + |
| Precedence | Must be interpreted | Encoded by token order |
| Parentheses | May be needed | Not needed for binary expression structure |
| Evaluation | Requires parsing rules | One stack-based scan |
| Direction | Depends on parser | Left to right |
Memory Tricks for Postfix Evaluation
Left to Right
Postfix Evaluation always scans left to right in the standard Stack algorithm.
Number = Push
Every operand goes onto the Stack.
Operator = Calculate
Pop two operands, calculate and Push the answer.
Right First, Left Second
The first popped value is the right operand.
Important Exam Questions With Answers
Q1. What is Postfix Expression Evaluation?
Postfix Expression Evaluation is the process of calculating a Postfix expression using a Stack. Operands are pushed and operators are evaluated by popping the required operands.
Q2. Which Data Structure is used for Postfix Evaluation?
Stack is commonly used for Postfix Expression Evaluation because it follows the Last In, First Out principle.
Q3. In which direction is a Postfix expression evaluated?
A Postfix expression is scanned from left to right using the standard Stack-based algorithm.
Q4. What is the time complexity of Postfix Evaluation?
The standard algorithm has O(n) time complexity because every token is processed once, assuming constant-time basic operations.
Q5. Explain Postfix Expression Evaluation Using Stack.
Postfix Expression Evaluation is performed using a Stack to store operands and intermediate results.
- Create an empty Stack.
- Read the expression from left to right.
- If the token is an operand, Push it.
- If the token is an operator, Pop two operands.
- Apply the operation and Push its result.
- Repeat until all tokens are processed.
- Return the single remaining Stack value.
Example:
First, 3 × 2 = 6. Then 5 + 6 = 11.
Q6. Why is operand order important in Postfix Evaluation?
Operand order determines the correct result for non-commutative operations such as subtraction and division.
During evaluation, the first popped value is the right operand and the second popped value is the left operand.
Example: 10 3 - gives 10 - 3 = 7, not 3 - 10 = -7.
Q7. Explain Postfix Expression Evaluation Using Stack With Algorithm, Example and Complexity.
A Postfix Expression is an expression in which binary operators appear after their operands.
Postfix Evaluation uses a Stack to perform operations in the order specified by the expression.
Algorithm
- Start with an empty Stack.
- Scan the Postfix expression from left to right.
- Push every operand onto the Stack.
- When a binary operator occurs, Pop two operands.
- Perform LEFT operator RIGHT.
- Push the calculated result.
- Continue until all tokens are processed.
- The single remaining value is the answer.
Example
Push 8 and 2. On /, calculate 8 / 2 = 4.
Push 3. On +, calculate 4 + 3 = 7.
Complexity
Time Complexity = O(n)
Auxiliary Space = O(n)
Advantages
- Simple Stack-based evaluation.
- No parentheses needed for unambiguous binary notation.
- Linear-time processing of basic expressions.
- Suitable for stack-based calculation systems.
Conclusion
Postfix Expression Evaluation is an important application of Stack that processes operands and operators according to LIFO behaviour.
Practice Questions With Answers
Evaluate: 6 2 3 + *
Show Answer
First, 2 + 3 = 5. Then 6 × 5 = 30. Final Answer = 30.
Evaluate: 15 5 / 4 +
Show Answer
15 / 5 = 3. Then 3 + 4 = 7.
Evaluate: 8 3 - 2 *
Show Answer
8 - 3 = 5. Then 5 × 2 = 10.
Evaluate: 2 3 ^ 4 +
Show Answer
2³ = 8. Then 8 + 4 = 12.
Is 5 + a valid Postfix expression?
Show Answer
No. The binary + operator needs two operands, but only one operand is available.
Evaluate: 9 3 / 2 4 * +
Show Answer
9 / 3 = 3. Then 2 × 4 = 8. Finally 3 + 8 = 11.
Quick Revision Before Semester Exam
Remember these important points before attempting Postfix Evaluation questions.
Postfix: Operator appears after operands.
Scanning: Read left to right.
Operand: Push onto Stack.
Operator: Pop two operands, calculate and Push result.
First Pop: Right operand.
Second Pop: Left operand.
Final Stack: Exactly one value.
Time Complexity: O(n) for standard evaluation.
Auxiliary Space: O(n) in the worst case.
Frequently Asked Questions
What is Postfix Expression Evaluation?
Postfix Expression Evaluation is the process of calculating an expression written with operators after their operands, commonly using a Stack.
Why is Stack used in Postfix Evaluation?
Stack stores operands and intermediate results. Its LIFO behaviour allows recent operands to be accessed when an operator is encountered.
What is the scanning direction in Postfix Evaluation?
Standard Postfix Evaluation scans from left to right.
How are subtraction and division evaluated?
The first popped value is the right operand. The second popped value is the left operand. Perform LEFT operator RIGHT.
What is the time complexity of Postfix Evaluation?
Standard Postfix Evaluation takes O(n) time for n tokens, assuming constant-time basic operations.
Can Postfix Evaluation handle multi-digit numbers?
Yes. A properly tokenised Postfix expression can use multi-digit operands. The C program in this chapter separates tokens using whitespace.
What happens if the Stack contains two values at the end?
The expression is incomplete or invalid for standard binary Postfix Evaluation. A valid completed expression must leave exactly one value.
What is the difference between Postfix and Prefix Evaluation?
Postfix Evaluation is normally performed from left to right. Prefix Evaluation is normally performed from right to left. Both can use Stacks.
Conclusion
Postfix Expression Evaluation Using Stack becomes easy when we remember how operands and operators are handled.
Start scanning the expression from left to right. Push every operand onto the Stack.
Whenever an operator appears, Pop the right operand first and then the left operand. Perform the calculation and Push the result.
After all tokens are processed, the final Stack must contain exactly one value.
Final Memory Trick: Number = Push, Operator = Pop Two, Calculate and Push.
For semester exams, practise dry-run tables, operand order and the Postfix Evaluation algorithm. These concepts are also useful in C programming and Stack-based problem solving.
