Infix to Postfix Conversion and Evaluation

 What is an Infix Expression?

An infix expression is the way we normally write mathematical expressions:

  • The operator is between the operands.

Examples of Infix expressions:

  • A + B

  • 5 * 3

  • 5 + 3 * 2

  • (A + B) * (C - D)

  • (7 + 3) * (5 - 2)

✅ This is natural for humans because we understand precedence (multiplication first, then addition) and use parentheses.

What is a Postfix Expression?

(also called Reverse Polish Notation)

A postfix expression places the operator after its operands.

  • No parentheses are needed.

  • No precedence rules needed — order of operations is built-in.

Examples of Postfix expressions:

  • A B + → (means A + B)

  • 5 3 * → (means 5 * 3)

  • A B + C D - * → (means (A + B) * (C - D))

  • 7 3 + 5 2 - * → (means (7 + 3) * (5 - 2))

✅ Computers prefer postfix because it’s very easy to evaluate using a stack.

🧠 Quick Comparison:

FeatureInfixPostfix
Operator positionBetween operandsAfter operands
Need for parentheses?Yes (sometimes)No
Operator precedence important?YesNo
ExampleA + BA B +
Human or Machine friendly?HumanMachine

Examples:
Infix                                                                Postfix
(A + B) * (C - D) / (E + F)                A B + C D - * E F + /
(5 + 2) * (8 - 3) / (4 + 1)                5 2 + 8 3 - * 4 1 + /
((A + B) * (C + D)) / ((E + F) * (G + H))  A B + C D + * E F + G H + * /
A + B * (C ^ D - E) ^ (F + G * H) - I      A B C D ^ E - F G H * + ^ * + I -


Algorithm for Infix to Postfix Conversion

We use a stack to hold operators and parentheses during the conversion.

Steps:

  1. Initialize an empty stack for operators and an empty postfix expression.

  2. Scan the infix expression from left to right.

  3. For each symbol in the infix expression:

    • If the symbol is an operand (letter or number), add it to the postfix expression.

    • If the symbol is (, push it onto the stack.

    • If the symbol is ):

      • Pop from the stack and append to the postfix expression until a ( is encountered.

      • Pop and discard the (.

    • If the symbol is an operator (+, -, *, /, ^):

      • While the stack is not empty, and the top of the stack has higher or equal precedence than the current operator:

        • Pop from the stack and append to the postfix expression.

      • Push the current operator onto the stack.

  4. After the entire infix expression is scanned:

    • Pop all remaining operators from the stack and append them to the postfix expression

Example:
(A + B) * (C - D)

InputStackPostfix
((
A(    A
+( +    A
B( +    A B
)    A B +
**    A B +
(* (    A B +
C* (            A B + C
-* ( -    A B + C
D* ( -        A B + C D
)*    A B + C D -
(end)    A B + C D - *


C Program Infix to Postfix Conversion
#include <stdio.h>
#include <ctype.h>  // for isalpha(), isdigit()
#include <string.h>

#define MAX 100

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

// Function to push into stack
void push(char c) {
    stack[++top] = c;
}

// Function to pop from stack
char pop() {
    if (top == -1)
        return -1;
    else
        return stack[top--];
}

// Function to return precedence of operators
int precedence(char c) {
    if (c == '^')
        return 3;
    else if (c == '*' || c == '/')
        return 2;
    else if (c == '+' || c == '-')
        return 1;
    else
        return 0;
}

void infixToPostfix(char infix[]) {
    char postfix[MAX];
    int i, j = 0;
    char c;
    
    for (i = 0; infix[i] != '\0'; i++) {
        c = infix[i];
        
        if (isalpha(c) || isdigit(c)) {
            postfix[j++] = c;  // Operand directly to postfix
        }
        else if (c == '(') {
            push(c);
        }
        else if (c == ')') {
            while (top != -1 && stack[top] != '(') {
                postfix[j++] = pop();
            }
            pop(); // pop '('
        }
        else { // Operator
            while (top != -1 && precedence(stack[top]) >= precedence(c)) {
                postfix[j++] = pop();
            }
            push(c);
        }
    }
    
    // Pop any remaining operators
    while (top != -1) {
        postfix[j++] = pop();
    }
    
    postfix[j] = '\0';  // End postfix expression
    
    printf("Postfix Expression: %s\n", postfix);
}

int main() {
    char infix[MAX];
    
    printf("Enter an Infix Expression: ");
    scanf("%s", infix);
    
    infixToPostfix(infix);
    
    return 0;
}
Output
Enter an Infix Expression: (A+B)*(C-D)/F^E
Postfix Expression: AB+CD-*FE^/

How to Evaluate a Postfix Expression?

We use a stack:

Algorithm Evaluation of Postfix Expression

  1. Scan the postfix expression left to right.

  2. For each symbol:

    • If it's an operand (number), push it onto the stack.

    • If it's an operator:

      • Pop the top two elements from the stack.

      • Apply the operator (second popped item operator first popped item).

      • Push the result back into the stack.

  3. At the end, the stack contains only one element — the final result.

Simple Example: single digit
7 8 + 3 2 + /

Step-by-step:

SymbolStackExplanation
77Push 7
87, 8Push 8
+157 + 8 = 15
315, 3Push 3
215, 3, 2Push 2
+15, 53 + 2 = 5
/315 / 5 = 3

✅ Final result: 3

Example Problems:

Infix                                Postfix                    Result
(5 * (6 + 2)) - (12 / 4)    5 6 2 + * 12 4 / -        37

(7 + 8) / (3 + 2)              7 8 + 3 2 + /                3

Quick Tips for Students:

  • Always push operands.

  • Always pop two operands for an operator.

  • Order matters: second popped value is first operand, first popped value is second operand.

  • Use a stack to keep things simple.

Implementation in C: single digit
#include <stdio.h>
#include <ctype.h>  // For isdigit()
#include <stdlib.h> // For atoi()

#define MAX 100

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

// Function to push into stack
void push(int value) {
    stack[++top] = value;
}

// Function to pop from stack
int pop() {
    return stack[top--];
}

// Function to evaluate postfix expression
int evaluatePostfix(char postfix[]) {
    int i;
    char ch;
    int val;
    
    for (i = 0; postfix[i] != '\0'; i++) {
        ch = postfix[i];
        
        if (isdigit(ch)) {
            // If operand, push onto stack
            push(ch - '0');  // Convert char to int
        }
        else if (ch == ' ') {
            // Ignore spaces
            continue;
        }
        else {
            // Operator encountered
            int val2 = pop();
            int val1 = pop();
            
            switch (ch) {
                case '+':
                    push(val1 + val2);
                    break;
                case '-':
                    push(val1 - val2);
                    break;
                case '*':
                    push(val1 * val2);
                    break;
                case '/':
                    push(val1 / val2);
                    break;
                case '^':
                    {
                        int result = 1;
                        for (int i = 0; i < val2; i++)
                            result *= val1;
                        push(result);
                        break;
                    }
            }
        }
    }
    
    return pop();
}

int main() {
    char postfix[MAX];
    
    printf("Enter a Postfix Expression (single-digit numbers and operators without spaces, like 562+*): ");
    scanf("%s", postfix);
    
    int result = evaluatePostfix(postfix);
    
    printf("Result of Postfix Evaluation: %d\n", result);
    
    return 0;
}

Output
Enter a Postfix Expression (single-digit numbers and operators without spaces, like 562+*): 562+*
Result of Postfix Evaluation: 40

How this code works:

  • Operands (digits 0-9) are pushed onto the stack.

  • Operators cause two elements to be popped, the operation applied, and the result pushed back.

  • At the end, the result is at the top of the stack.

Important Notes for Students:

  • This code assumes only single-digit numbers.

  • For multi-digit numbers, you can modify it to read space-separated tokens.

  • Operators supported are +, -, *, /, and ^ (power).


Improved C code that can handle multi-digit numbers in the postfix expression (numbers are space-separated):

#include <stdio.h>
#include <stdlib.h>  // For atoi()

#define MAX 100

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

// Function to push value into stack
void push(int value) {
    
    if (top >= MAX - 1) {
        printf("Stack Overflow\n");
        exit(1);
    }
    stack[++top] = value;
    
}

// Function to pop value from stack
int pop() {
    
    if (top < 0) {
        printf("Stack Underflow\n");
        exit(1);
    }
    return stack[top--];
}

// Function to evaluate postfix expression
int evaluatePostfix(char postfix[]) {
    int i = 0;
    
    while (postfix[i] != '\n') {
        // If space, skip
        if (postfix[i] == ' ') {
            i++;
            continue;
        }
        
        // If digit, read full number (multi-digit)
        if (postfix[i] >= '0' && postfix[i] <= '9') {
            int num = 0;
            while (postfix[i] >= '0' && postfix[i] <= '9') {
                num = num * 10 + (postfix[i] - '0');
                i++;
            }
           
            push(num);
        }
        else {
            // Operator encountered
            int val2 = pop();
            int val1 = pop();
            
            switch (postfix[i]) {
                case '+':
                    push(val1 + val2);
                    break;
                case '-':
                    push(val1 - val2);
                    break;
                case '*':
                    push(val1 * val2);
                    break;
                case '/':
                    push(val1 / val2);
                    break;
                case '^':
                    {
                        int result = 1;
                        for (int j = 0; j < val2; j++)
                            result *= val1;
                        push(result);
                        break;
                    }
                default:
                    printf("Unknown operator %c\n", postfix[i]);
                    exit(1);
            }
            i++;
        }
    }
    
    return pop();
}

int main() {
    char postfix[MAX];
    
    printf("Enter a Postfix Expression (numbers and operators separated by spaces):\n");
    fgets(postfix, MAX, stdin);
    
    int result = evaluatePostfix(postfix);
    
    printf("Result of Postfix Evaluation: %d\n", result);
    
    return 0;
}
Output:
Enter a Postfix Expression (numbers and operators separated by spaces):
12 13 + 3 15 * +
Result of Postfix Evaluation: 70

Comments

Post a Comment

Popular posts from this blog

Data Structures Lab PCCSL307 KTU 2024 Scheme - Dr Binu V P

About Me    Learn the theory Data Structures and Algorithms PCCST303 Scheme and Assessments Experiment List and References Lab Assignments Format of the Lab Record Lab Cycle ( Mandatory Programs) 1.Polynomial Addition Using Arrays 2.Sparse Matrix- Transpose and Addition 3.Stack    Implement  stack using array    Infix to Postfix Conversion and Evaluation 4.Queue    Queue using array     Circular Queue using array     Double ended Queue using array 5.Singly Linked List      Singly  Linked list and operations     Stack using linked list     Queue using linked list    Polynomial addition using linked list    Polynomial multiplication using linked list     Priority Queue-Post office customers simulation     Circular Queue using Linked List 6. Doubly Linked List      Doubly Linked List- Operations     Double Ended Queue ...
Read more

Sparse Matrix - Transpose and Addition

Image
  A sparse matrix is a special type of matrix in which most of the elements are zero or have some default value. In contrast, a dense matrix is one in which most of the elements are non-zero. Sparse matrices are used in various fields, including computer science, numerical analysis, and scientific computing, when dealing with large datasets or systems where efficiency and memory usage are crucial.   As a rule of thumb, if 2/3 of the total elements in a matrix are zeros, it can be called a sparse matrix . Using a sparse matrix representation — where only the non-zero values are stored — the space used for representing data and the time for scanning the matrix are reduced significantly. In many real-world problems — like graphs, networks, or scientific simulations — the majority of elements in the matrix are zero . Such a matrix is called a Sparse Matrix . Formally: A matrix in which the number of zero elements is significantly greater than the number of non-zero elements. ...
Read more

Polynomial Addition using Arrays

Polynomial  Addition We can represent a polynomial as a collection of terms and every term is having a coefficient and exponent. So, we can represent this as a list of terms having coefficients and exponents.  Each term of a polynomial (like 3 x 2 3x^2 , 5 x 1 5x^1 , − 7 x 0 -7x^0 ) can be stored in a structure having two parts: coefficient (like 3, 5, -7) exponent (like 2, 1, 0) An array of such structures represents the whole polynomial. Structure Definition (Example in C) struct Term { int coeff; // Coefficient of the term int expo; // Exponent of the term }; And then you can declare: struct Term poly1 [10], poly2 [10], polyResult [20]; to represent polynomials. Algorithm to Add Two Polynomials Assumption : Both polynomials are sorted in decreasing order of exponents . Steps : Initialize three pointers (indexes): i = 0 for first polynomial (poly1), j = 0 for second polynomial (poly2), k = 0 for result polynomial (polyR...
Read more