Postfix Expression Evaluation Using Stack in Data Structure

CHAPTER 25 • DATA STRUCTURE

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.

Postfix Expression Stack Evaluation Algorithms Dry Runs C Programming

Suppose your teacher writes the following expression on the board:

5 3 2 * +

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.

Quick Answer: Postfix Expression Evaluation Using Stack is a method of calculating a Postfix expression by scanning it from left to right. When an operand appears, it is pushed onto the Stack. When a binary operator appears, two operands are popped, the operation is performed, and the result is pushed back onto the Stack. After all tokens are processed, one value remains as the final answer.

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 Using Stack in Data Structure

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.

A B +

This represents the normal Infix expression A + B.

Understand With a Simple Example

Infix

5 + 3

Operator is placed between operands.

Postfix

5 3 +

Operator is placed after the operands.

Evaluation

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

Figure 1: Postfix expression 5 3 +. The operator comes after its operands.
Memory Trick:

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.

Main Working Rule:

Operand → Push into Stack.

Operator → Pop two operands, calculate, then Push the result.

Step-by-Step Working

1
Create an empty Stack.

Initially, there are no values inside the Stack.

2
Read from left to right.

Process the expression one token at a time.

3
Push each operand.

If the current token is a number, insert it into the Stack.

4
Process an operator.

Pop the first value as RIGHT and the second value as LEFT.

5
Calculate and Push.

Perform LEFT operator RIGHT and Push the result into the Stack.

6
Return the final result.

After processing all tokens, a valid expression must leave exactly one value.

Visualise the Stack

Consider the following Postfix expression:

5 3 +
Push 5
5
→
Push 3
3
5
→
Calculate +
8
Figure 2: Push 5, Push 3, calculate 5 + 3 and Push 8.

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.

Final Result = 8

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.

Exam Memory Trick:

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

5 6 2 + * 12 4 / -

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

1
Push 5, 6 and 2.

These are operands, so store all three in the Stack.

2
Process + operator.

Pop 2 and 6. Calculate 6 + 2 = 8. Push 8.

3
Process * operator.

Pop 8 and 5. Calculate 5 × 8 = 40. Push 40.

4
Push 12 and 4.

The Stack contains 40, 12 and 4.

5
Process / operator.

Pop 4 and 12. Calculate 12 / 4 = 3. Push 3.

6
Process - operator.

Pop 3 and 40. Calculate 40 - 3 = 37. Push 37.

Final Answer:
37

Since only one value remains in the Stack, the expression has been successfully evaluated.

Final Stack Diagram

TOP
37
Figure 3: Final Stack containing a single result, 37.
Important Exam Tip:

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

12 3 4 * +

Follow these steps:

1

Push 12, 3 and 4.

2

* appears. Calculate 3 × 4 = 12.

3

+ appears. Calculate 12 + 12 = 24.

Answer:
24

Example 3: Division and Subtraction

20 5 - 3 /
Token Action Stack
20Push20
5Push20, 5
-20 - 5 = 1515
3Push15, 3
/15 / 3 = 55
Answer:
5

Example 4: Exponentiation

3 2 ^ 4 +

Here, ^ represents exponentiation in the mathematical expression.

1

Push 3 and 2.

2

Process ^. Calculate 3² = 9.

3

Push 4.

4

Process +. Calculate 9 + 4 = 13.

Answer:
13

Example 5: Negative Number

-5 2 * 6 +

In this expression, -5 is a single negative-number token, not the binary subtraction operator.

First, -5 × 2 = -10. Then -10 + 6 = -4.

Answer:
-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.

Remember:

First Pop = Right Operand

Second Pop = Left Operand

Subtraction Example

10 3 -

Push 10, then Push 3. The TOP contains 3.

Correct

10 - 3 = 7

LEFT = 10
RIGHT = 3

Incorrect

3 - 10 = -7

This reverses the operand positions.

Division Example

20 4 /

First Pop returns 4, so RIGHT = 4.

Second Pop returns 20, so LEFT = 20.

LEFT / RIGHT = 20 / 4 = 5

Operand Order Memory Trick

Pop Right → Pop Left → Left OP Right
Remember:

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.

Important: The -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

1
isOperator()

Checks whether a token is one of the supported binary operators.

2
strtok()

Separates the entered expression into tokens using spaces and other whitespace.

3
strtod()

Converts a numeric token into a double value.

4
evaluatePostfix()

Uses the Stack to process operands and perform mathematical operations.

5
main()

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
Program Limitations:

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

5 +

The + operator needs two operands, but only one is available.

2. Extra Operands

3 4

Both operands remain without an operator. The final Stack has two values.

3. Division by Zero

12 0 /

The denominator becomes zero, so evaluation must report an error.

4. Invalid Token

5 A +

A cannot be evaluated numerically unless a value has been supplied.

5. Reversed Operand Order

10 3 -

The correct result is 7, not -7.

6. Incorrect Scanning

Left → Right

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.

Final Stack Size = 1
Memory Trick:

"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.

Time Complexity = O(n)

Space Complexity

A Stack temporarily stores operands and intermediate results.

In the worst case, Stack storage grows linearly with the number of tokens.

Auxiliary Space = O(n)
Operation Time Complexity
PushO(1)
PopO(1)
PeekO(1)
Process One OperatorO(1) for basic arithmetic
Evaluate n TokensO(n)
Technical Note:

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.

Application 01

Stack-Based Calculators

Postfix notation is used in Reverse Polish Notation calculators where values are stored and combined through a Stack.

Application 02

Compiler and Interpreter Concepts

Stack-based evaluation helps explain how programming expressions can be converted into executable operations.

Application 03

Expression Processing

Postfix notation provides an ordered representation that does not require parentheses for unambiguous binary expressions.

Application 04

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
One-Line Difference: Infix requires interpreting operator precedence and grouping, while Postfix already expresses the operation order through the placement of operators.

Memory Tricks for Postfix Evaluation

Memory Trick 1

Left to Right

Postfix Evaluation always scans left to right in the standard Stack algorithm.

Memory Trick 2

Number = Push

Every operand goes onto the Stack.

Memory Trick 3

Operator = Calculate

Pop two operands, calculate and Push the answer.

Memory Trick 4

Right First, Left Second

The first popped value is the right operand.

Scan → Push → Pop → Calculate → Push

Important Exam Questions With Answers

2 Marks

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.

2 Marks

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.

2 Marks

Q3. In which direction is a Postfix expression evaluated?

A Postfix expression is scanned from left to right using the standard Stack-based algorithm.

2 Marks

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.

5 Marks

Q5. Explain Postfix Expression Evaluation Using Stack.

Postfix Expression Evaluation is performed using a Stack to store operands and intermediate results.

  1. Create an empty Stack.
  2. Read the expression from left to right.
  3. If the token is an operand, Push it.
  4. If the token is an operator, Pop two operands.
  5. Apply the operation and Push its result.
  6. Repeat until all tokens are processed.
  7. Return the single remaining Stack value.

Example:

5 3 2 * +

First, 3 × 2 = 6. Then 5 + 6 = 11.

Answer = 11
5 Marks

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.

10 Marks

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

  1. Start with an empty Stack.
  2. Scan the Postfix expression from left to right.
  3. Push every operand onto the Stack.
  4. When a binary operator occurs, Pop two operands.
  5. Perform LEFT operator RIGHT.
  6. Push the calculated result.
  7. Continue until all tokens are processed.
  8. The single remaining value is the answer.

Example

8 2 / 3 +

Push 8 and 2. On /, calculate 8 / 2 = 4.

Push 3. On +, calculate 4 + 3 = 7.

Final Answer = 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

Practice 1

Evaluate: 6 2 3 + *

Show Answer

First, 2 + 3 = 5. Then 6 × 5 = 30. Final Answer = 30.

Practice 2

Evaluate: 15 5 / 4 +

Show Answer

15 / 5 = 3. Then 3 + 4 = 7.

Practice 3

Evaluate: 8 3 - 2 *

Show Answer

8 - 3 = 5. Then 5 × 2 = 10.

Practice 4

Evaluate: 2 3 ^ 4 +

Show Answer

2³ = 8. Then 8 + 4 = 12.

Practice 5

Is 5 + a valid Postfix expression?

Show Answer

No. The binary + operator needs two operands, but only one operand is available.

Practice 6

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.

Tags

Post a Comment

0 Comments
* Please Don't Spam Here. All the Comments are Reviewed by Admin.
Join Telegram Exam updates and free resources