C Program to Evaluate Postfix Expression

A C program to evaluate postfix expression uses a stack to push operands and pop them when an operator is found, performing the operation and pushing the result back; for example, use push(), pop(), and scan the expression from left to right to compute the final value.

Examples

Input23+

Output5

Input6523+8*+3+*

Output288

Input82/

Output4

How to Think About It

To evaluate a postfix expression, read it from left to right. When you see a number, push it onto a stack. When you see an operator, pop the top two numbers from the stack, apply the operator, and push the result back. At the end, the stack has the final answer.

Algorithm

1

Initialize an empty stack.

2

Scan the postfix expression from left to right.

3

If the scanned character is an operand, push it onto the stack.

4

If the scanned character is an operator, pop two operands from the stack, apply the operator, and push the result back.

5

After the entire expression is scanned, the stack's top element is the result.

6

Return or print the result.

Code

c

#include <stdio.h>
#include <ctype.h>
#define MAX 100

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

void push(int val) {
    stack[++top] = val;
}

int pop() {
    return stack[top--];
}

int evaluatePostfix(char* expr) {
    int i = 0;
    while (expr[i] != '\0') {
        if (isdigit(expr[i])) {
            push(expr[i] - '0');
        } else {
            int val2 = pop();
            int val1 = pop();
            switch(expr[i]) {
                case '+': push(val1 + val2); break;
                case '-': push(val1 - val2); break;
                case '*': push(val1 * val2); break;
                case '/': push(val1 / val2); break;
            }
        }
        i++;
    }
    return pop();
}

int main() {
    char expr[] = "6523+8*+3+*";
    printf("Result: %d\n", evaluatePostfix(expr));
    return 0;
}

Output

Result: 288

Dry Run

Let's trace the postfix expression "6523+8*+3+*" through the code

1

Push operands

Push 6, 5, 2, 3 onto stack: [6,5,2,3]

2

Operator '+'

Pop 3 and 2, add: 2+3=5, push 5: [6,5,5]

3

Push operand 8

Push 8: [6,5,5,8]

4

Operator '*'

Pop 8 and 5, multiply: 5*8=40, push 40: [6,5,40]

5

Operator '+'

Pop 40 and 5, add: 5+40=45, push 45: [6,45]

6

Push operand 3

Push 3: [6,45,3]

7

Operator '+'

Pop 3 and 45, add: 45+3=48, push 48: [6,48]

8

Operator '*'

Pop 48 and 6, multiply: 6*48=288, push 288: [288]

9

Final result

Pop 288 as final result

Stack after operation
[6]
[6,5]
[6,5,2]
[6,5,2,3]
[6,5,5]
[6,5,5,8]
[6,5,40]
[6,45]
[6,45,3]
[6,48]
[288]

Why This Works

Step 1: Using a stack for operands

Operands are pushed onto a stack to keep track of values until an operator is found.

Step 2: Applying operators

When an operator appears, the top two operands are popped, the operation is done, and the result is pushed back.

Step 3: Final result on stack

After processing the whole expression, the stack contains the final evaluated result.

Alternative Approaches

Using linked list stack

c

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* top = NULL;

void push(int val) {
    Node* newNode = malloc(sizeof(Node));
    newNode->data = val;
    newNode->next = top;
    top = newNode;
}

int pop() {
    if (!top) return -1;
    int val = top->data;
    Node* temp = top;
    top = top->next;
    free(temp);
    return val;
}

int evaluatePostfix(char* expr) {
    int i = 0;
    while (expr[i]) {
        if (isdigit(expr[i])) push(expr[i] - '0');
        else {
            int b = pop();
            int a = pop();
            switch(expr[i]) {
                case '+': push(a + b); break;
                case '-': push(a - b); break;
                case '*': push(a * b); break;
                case '/': push(a / b); break;
            }
        }
        i++;
    }
    return pop();
}

int main() {
    char expr[] = "23+";
    printf("Result: %d\n", evaluatePostfix(expr));
    return 0;
}

Linked list stack avoids fixed size limit but uses dynamic memory.

Using recursion to evaluate

c

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

int i = 0;

int evaluate(char* expr) {
    char c = expr[i++];
    if (isdigit(c)) return c - '0';
    int left = evaluate(expr);
    int right = evaluate(expr);
    switch(c) {
        case '+': return left + right;
        case '-': return left - right;
        case '*': return left * right;
        case '/': return left / right;
    }
    return 0;
}

int main() {
    char expr[] = "+23"; // prefix example
    printf("Result: %d\n", evaluate(expr));
    return 0;
}

This is for prefix expressions, showing a different approach.

Complexity: O(n) time, O(n) space

Time Complexity

The program scans the expression once, performing constant time operations per character, so time is O(n) where n is expression length.

Space Complexity

The stack stores operands and intermediate results, requiring O(n) space in the worst case.

Which Approach is Fastest?

Array-based stack is faster due to less overhead, while linked list stack uses dynamic memory but is more flexible.

Approach	Time	Space	Best For
Array Stack	O(n)	O(n)	Simple fixed size expressions
Linked List Stack	O(n)	O(n)	Dynamic size expressions
Recursive (prefix)	O(n)	O(n)	Prefix expressions, different use case