ds_4.c

/*
 * Program: Infix to Postfix Conversion using Stack
 *
 * This program converts an infix arithmetic expression to its equivalent postfix (Reverse Polish) notation.
 * It uses a character stack to manage operators and parentheses during the conversion process.
 *
 * Functions:
 * - push(char c): Pushes a character onto the stack.
 * - pop(): Pops and returns the top character from the stack.
 * - peek(): Returns the top character of the stack without removing it.
 * - precedence(char op): Returns the precedence level of an operator.
 * - isOperator(char c): Checks if a character is a valid operator.
 * - infixToPostfix(char* infix, char* postfix): Converts an infix expression to postfix notation.
 *
 * The main function reads an infix expression from the user, calls the conversion function,
 * and prints the resulting postfix expression.
 *
 * Limitations:
 * - Supports single-character operands (e.g., a, b, 1, 2).
 * - Handles operators: +, -, *, /, ^ and parentheses.
 * - Maximum expression length is defined by MAX (100).
 */
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAX 100

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

void push(char c)
{
    if (top < MAX - 1)
        stack[++top] = c;
}

char pop()
{
    if (top >= 0)
        return stack[top--];
    return '\0';
}

char peek()
{
    if (top >= 0)
        return stack[top];
    return '\0';
}

int precedence(char op)
{
    switch (op)
    {
    case '^':
        return 3;
    case '*':
    case '/':
        return 2;
    case '+':
    case '-':
        return 1;
    default:
        return 0;
    }
}

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

void infixToPostfix(char *infix, char *postfix)
{
    int i, k = 0;
    char c;
    for (i = 0; infix[i] != '\0'; i++)
    {
        c = infix[i];
        if (isspace(c))
            continue;
        if (isalnum(c))
        {
            postfix[k++] = c;
        }
        else if (c == '(')
        {
            push(c);
        }
        else if (c == ')')
        {
            while (top != -1 && peek() != '(')
                postfix[k++] = pop();
            pop(); // remove '('
        }
        else if (isOperator(c))
        {
            while (top != -1 && precedence(peek()) >= precedence(c))
            {
                if (c == '^' && peek() == '^')
                    break; // right associative
                postfix[k++] = pop();
            }
            push(c);
        }
    }
    while (top != -1)
        postfix[k++] = pop();
    postfix[k] = '\0';
}

int main()
{
    char infix[MAX], postfix[MAX];
    printf("Enter infix expression: ");
    fgets(infix, MAX, stdin);
    infix[strcspn(infix, "\n")] = '\0'; // remove newline
    infixToPostfix(infix, postfix);
    printf("Postfix expression: %s\n", postfix);
    return 0;
}