Infix to Prefix Conversion and Evaluation

 

🔶 Infix to Prefix Expression Conversion

✅ Definitions:

  • Infix Expression: Operators are written in-between the operands.
    Example: A + B

  • Prefix Expression (Polish Notation): Operators are written before their operands.
    Example: + A B

✅ Why Convert Infix to Prefix?

Computers evaluate prefix or postfix expressions more easily because they don’t need parentheses and respect operator precedence inherently.

✅ Steps to Convert Infix to Prefix:

  1. Reverse the infix expression.

  2. Change every ( to ) and vice versa.

  3. Convert the modified expression to postfix.

  4. Reverse the postfix expression to get prefix.

✅ Operator Precedence and Associativity:

Operator            Precedence        Associativity
^            High            Right to Left
* / %            Medium            Left to Right
+ -            Low            Left to Right

✅ Helper Functions:

You’ll need:

  • A function to check if a character is operand.

  • A function to get precedence of operators.

  • A function to convert infix to postfix (used on reversed expression).

  • Stack data structure.

✅ Example 1: Infix to Prefix Conversion

🔸 Infix Expression:

A + B * C

🔹 Step-by-step Conversion:

1. Reverse the Infix Expression:

Original:      A + B * C
Reversed:      C * B + A

2. Swap '(' and ')' — not needed here as there are no brackets.

3. Convert Reversed Infix to Postfix:

Infix (reversed):  C * B + A
Postfix of that:   CB*A+

4. Reverse the Postfix to get Prefix:

Reverse "CB*A+" → "+A*BC"

✅ Final Prefix Expression: 

+A*BC

🔷 Sample C Code for Infix to Prefix Conversion

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

#define MAX 100

// Stack for characters
char stack[MAX];
int top = -1;

void push(char ch) {
    stack[++top] = ch;
}

char pop() {
    if (top == -1) return -1;
    return stack[top--];
}

char peek() {
    return stack[top];
}

int isOperator(char ch) {
    return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^';
}

int precedence(char ch) {
    if (ch == '^') return 3;
    if (ch == '*' || ch == '/' || ch == '%') return 2;
    if (ch == '+' || ch == '-') return 1;
    return 0;
}

int isRightAssociative(char op) {
    return op == '^';
}

int isOperand(char ch) {
    return isalpha(ch) || isdigit(ch);
}

// Reverse a string
void reverse(char* exp) {
    int len = strlen(exp);
    for (int i = 0; i < len / 2; i++) {
        char temp = exp[i];
        exp[i] = exp[len - i - 1];
        exp[len - i - 1] = temp;
    }
}

// Swap '(' and ')' in a string
void swapBrackets(char* exp) {
    for (int i = 0; exp[i]; i++) {
        if (exp[i] == '(')
            exp[i] = ')';
        else if (exp[i] == ')')
            exp[i] = '(';
    }
}

// Convert Infix to Postfix
void infixToPostfix(char* infix, char* postfix) {
    int j = 0;
    for (int i = 0; infix[i]; i++) {
        char ch = infix[i];

        if (isOperand(ch)) {
            postfix[j++] = ch;
        }
        else if (ch == '(') {
            push(ch);
        }
        else if (ch == ')') {
            while (top != -1 && peek() != '(')
                postfix[j++] = pop();
            pop(); // remove '('
        }
        else if (isOperator(ch)) {
            while (top != -1 && isOperator(peek()) &&
                   (precedence(peek()) > precedence(ch) ||
                    (precedence(peek()) == precedence(ch) && !isRightAssociative(ch)))) {
                postfix[j++] = pop();
            }
            push(ch);
        }
    }

    while (top != -1)
        postfix[j++] = pop();
    
    postfix[j] = '\0';
}

// Infix to Prefix
void infixToPrefix(char* infix, char* prefix) {
    char revInfix[MAX], postfix[MAX];

    strcpy(revInfix, infix);
    reverse(revInfix);
    swapBrackets(revInfix);
    top = -1; // reset stack
    infixToPostfix(revInfix, postfix);
    reverse(postfix);
    strcpy(prefix, postfix);
}

// ---------- MAIN FUNCTION ----------
int main() {
    char infix[MAX], prefix[MAX];

    printf("Enter an infix expression: ");
    scanf("%s", infix);

    infixToPrefix(infix, prefix);

    printf("Prefix expression: %s\n", prefix);

    return 0;
}

Output
Enter an infix expression: a+b*c
Prefix expression: +a*bc

🔶 Evaluation of Prefix Expression

✅ Steps:

  1. Scan prefix expression right to left.

  2. If it's an operand, push it on the stack.

  3. If it's an operator, pop two operands, apply operator, push result back.

Prefix Expression Evaluation

Let’s evaluate a prefix expression that uses numbers.

🔸 Prefix Expression:

+ 9 * 2 3

This corresponds to the infix:

9 + (2 * 3) = 9 + 6 = 15

🔹 Step-by-step Evaluation:

We process from right to left.

  1. Stack: []

  2. Read 3 → push → Stack: [3]

  3. Read 2 → push → Stack: [3, 2]

  4. Read * → pop 2 and 3 → 2 * 3 = 6 → push → Stack: [6]

  5. Read 9 → push → Stack: [6, 9]

  6. Read + → pop 9 and 6 → 9 + 6 = 15 → push → Stack: [15]

✅ Final Result:

15

 Prefix Expression Evaluation in C 

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

#define MAX 100

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

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

int pop() {
    if (top == -1) {
        printf("Error: Stack underflow\n");
        exit(1);
    }
    return stack[top--];
}

int isOperator(char ch) {
    return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^';
}

// Evaluate prefix expression
int evaluatePrefix(char* expr) {
    int i;
    int len = strlen(expr);

    // Traverse from right to left
    for (i = len - 1; i >= 0; i--) {
        char ch = expr[i];

        if (isspace(ch))
            continue;

        if (isdigit(ch)) {
            push(ch - '0'); // Convert char to int
        }
        else if (isOperator(ch)) {
            int op1 = pop();
            int op2 = pop();
            int result;

            switch (ch) {
                case '+': result = op1 + op2; break;
                case '-': result = op1 - op2; break;
                case '*': result = op1 * op2; break;
                case '/': result = op1 / op2; break;
                case '^': result = pow(op1, op2); break;
                default:
                    printf("Invalid operator: %c\n", ch);
                    exit(1);
            }
            push(result);
        }
        else {
            printf("Invalid character in expression: %c\n", ch);
            exit(1);
        }
    }

    return pop();
}

// ---------- MAIN FUNCTION ----------
int main() {
    char prefix[MAX];

    printf("Enter a prefix expression (single-digit operands): ");
    fgets(prefix, MAX, stdin);
    prefix[strcspn(prefix, "\n")] = '\0'; // remove newline

    int result = evaluatePrefix(prefix);
    printf("Result of prefix evaluation: %d\n", result);

    return 0;
}

Output:

Enter a prefix expression (single-digit operands): +9*23
Result of prefix evaluation: 15

Comments

Post a Comment

Popular posts from this blog

Data Structures and Algorithms PCCST303 KTU 2024 Scheme- Dr Binu V P

About Me Syllabus and evaluation scheme  1.Basic Concepts of Data Structures     Data structures and data abstraction     Time and Space Complexity     Asymptotic Analysis and Asymptotic Notations     Best case, Worst case and Average Case Analysis of Algorithms     Frequency Count Method of Algorithm Analysis     Polynomial Representation using arrays      Polynomial Addition using arrays      Sparse Addition and Transpose     Stacks     Multi Stacks      Queue using array      Circular Queue using array      Double ended Queue using array     Infix to postfix and postfix evaluation     Infix to prefix and prefix evaluation    2.Linked List and Memory Management          Self Referential Data Structures     Dynamic Memory Allocation in C     Singly Linked...
Read more

Performance Analysis - Time and Space Complexity

Image
  📚 Performance Analysis  Performance analysis means studying how efficient an algorithm or data structure is. Mainly, we check two things: Time Complexity — How much time (number of operations) the algorithm takes. Space Complexity — How much memory (space) the algorithm uses. ✅ Goal : To predict how the algorithm will behave as the input size grows without running the code. 📍 1. Time Complexity Measures the amount of time an algorithm takes to complete. It is expressed as a function of the input size n . We usually use Big-O notation (e.g., O(n), O(log n), O(n²)) to express it. ⏳ Why it matters? Because we want algorithms that are fast even for large inputs . Example for Time Complexity: Suppose we have a simple loop: for ( int i = 0 ; i < n; i++) { printf ( "%d " , i); } The loop runs n times . Each printf is a constant-time operation. So, Time Complexity = O(n) (linear time). Types of Common Time Complexities...
Read more

Data Structures and Data Abstraction

  What is a Data Structure? A data structure is a way to organize, manage, and store data so that it can be used efficiently . It defines how data is arranged in memory and how operations like insertion , deletion , searching , and updating can be performed. In simple words: Data structures are like containers that hold data together in a certain format so that computers can easily access and modify them.   More formally   "A data structure is a mathematical and logical model of a particular organization of data. It describes the relationship among the data elements, and the operations that can be performed on them." ➔ Key points: Organization of data. Logical relationship between data elements. Set of operations that can be applied (like insert, delete, search, etc.). Key Points about Data Structures: They help in organizing large amounts of data easily. They improve the efficiency of algorithms. They decide how fast and efficient prog...
Read more