C Program to Convert Infix to Postfix Expression

Introduction

Infix expressions are the standard arithmetic expressions where operators are placed between operands, such as A + B. Postfix expressions, also known as Reverse Polish Notation (RPN), place operators after their operands, such as AB+. Converting infix expressions to postfix expressions is essential in compiler design and expression evaluation because postfix expressions eliminate the need for parentheses and make the evaluation of expressions easier using stacks.

Example:

• Input: Infix expression A + B * C
• Output: Postfix expression ABC*+

Problem Statement

Create a C program that:

• Converts an infix expression to a postfix expression using a stack.
• Handles operators like +, -, *, /, and parentheses ( and ).

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> and #include <stdlib.h> for standard input-output functions.
2. Define Constants and Global Variables: Define the maximum size of the stack and the precedence of operators.
3. Implement the Stack Operations:

• Push: Add an operator to the stack.
• Pop: Remove and return the top operator from the stack.
• Peek/Top: Return the top operator without removing it.
• IsEmpty: Check if the stack is empty.

4. Implement the Infix to Postfix Conversion:

• Iterate over each character of the infix expression.
• Use the stack to manage operators and convert the expression to postfix.

5. Create a Main Function: Allow the user to input an infix expression and display the corresponding postfix expression.

C Program to Convert Infix to Postfix Expression

#include <stdio.h> #include <stdlib.h> #include <ctype.h> // Step 2: Define Constants and Global Variables #define MAX 100 // Maximum size of the stack char stack[MAX]; int top = -1; // Function to push an element onto the stack void push(char item) { if (top >= MAX - 1) { printf("Stack overflow!\n"); return; } stack[++top] = item; } // Function to pop an element from the stack char pop() { if (top < 0) { printf("Stack underflow!\n"); return -1; } return stack[top--]; } // Function to peek the top element of the stack char peek() { if (top < 0) { return -1; } return stack[top]; } // Function to check if the stack is empty int isEmpty() { return top == -1; } // Function to return the precedence of operators int precedence(char op) { switch (op) { case '+': case '-': return 1; case '*': case '/': return 2; case '^': return 3; default: return 0; } } // Function to check if the character is an operator int isOperator(char ch) { return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^'; } // Function to convert infix expression to postfix expression void infixToPostfix(char* infix, char* postfix) { int i = 0, j = 0; char ch; while ((ch = infix[i++]) != '\0') { if (isalnum(ch)) { // If the character is an operand, add it to the postfix expression postfix[j++] = ch; } else if (ch == '(') { // If the character is '(', push it onto the stack push(ch); } else if (ch == ')') { // If the character is ')', pop and output from the stack until '(' is found while (!isEmpty() && peek() != '(') { postfix[j++] = pop(); } pop(); // Pop '(' from the stack } else if (isOperator(ch)) { // If the character is an operator while (!isEmpty() && precedence(peek()) >= precedence(ch)) { postfix[j++] = pop(); } push(ch); } } // Pop all the remaining operators from the stack while (!isEmpty()) { postfix[j++] = pop(); } postfix[j] = '\0'; // Null-terminate the postfix expression } int main() { char infix[MAX], postfix[MAX]; printf("Enter an infix expression: "); gets(infix); // Read the infix expression from the user infixToPostfix(infix, postfix); // Convert infix to postfix printf("Postfix expression: %s\n", postfix); // Display the postfix expression return 0; // Return 0 to indicate successful execution } 

Explanation

Step 2: Define Constants and Global Variables

• The MAX constant defines the maximum size of the stack.
• The stack is implemented as a character array stack[MAX], and the top variable is initialized to -1 to indicate that the stack is initially empty.

Function to Push an Element onto the Stack

• The push function adds an element to the top of the stack if the stack is not full.

Function to Pop an Element from the Stack

• The pop function removes and returns the top element from the stack if the stack is not empty.

Function to Peek the Top Element of the Stack

• The peek function returns the top element of the stack without removing it.

Function to Check if the Stack is Empty

• The isEmpty function returns 1 if the stack is empty (top == -1), otherwise returns 0.

Function to Return the Precedence of Operators

• The precedence function returns the precedence level of an operator. Operators with higher precedence are evaluated before those with lower precedence.

Function to Check if a Character is an Operator

• The isOperator function returns 1 if the character is an operator (+, -, *, /, ^), otherwise returns 0.

Function to Convert Infix Expression to Postfix Expression

• The infixToPostfix function converts an infix expression to a postfix expression using the stack.
• The function iterates through each character of the infix expression, handling operands, operators, and parentheses appropriately:
  • Operands are directly added to the postfix expression.
  • Left parentheses are pushed onto the stack.
  • Right parentheses cause the stack to pop operators until a left parenthesis is encountered.
  • Operators are pushed onto the stack after popping operators of higher or equal precedence.
• Finally, any remaining operators in the stack are popped and added to the postfix expression.

Main Function

• The main function reads an infix expression from the user, converts it to postfix using the infixToPostfix function, and displays the resulting postfix expression.

Output Example

Example Output:

Enter an infix expression: A+B*(C^D-E) Postfix expression: ABCD^E-*+ 

Conclusion

This C program demonstrates how to convert an infix expression to a postfix expression using a stack. The program handles different operators and parentheses, making it a useful example for understanding expression conversion and stack operations in C programming.