Program to Convert Infix to Postfix using Stack in C
This article explains the C program for converting infix expressions to postfix notation using a stack. By the end of this guide, you’ll understand how stacks are used to handle operator precedence and associativity effectively. Let’s break the code into meaningful sections for clarity.
Understanding Infix and Postfix Notation
- Infix Notation: Operators are placed between operands. Example:
A + B
. - Postfix Notation: Operators follow their operands. Example:
AB+
.
Why Convert? Postfix expressions eliminate the need for parentheses and are easier for machines to evaluate using stacks.
Core Components of the Code
In this section any postfix notation you will enter, the following code will provide the output in term of result. Let start with first component
1. Stack Data Structure
The stack is implemented using an array with the following operations:
typedef struct { char data[MAX]; // Array to hold stack elements int top; // Index of the top element } Stack; |
2. Key Stack Operations:
- Push: Adds an element to the top of the stack.
- Pop: Removes and returns the top element.
- Peek: Returns the top element without removing it.
void push(Stack *stack, char value) { if (stack->top == MAX – 1) { printf(“Stack overflow\n”); return; } stack->data[stack->top + 1] = value; stack->top++; } char pop(Stack *stack) { char peek(Stack *stack) { |
Explanation:
push
Function: Adds a value to the stack. It checks if the stack is full (stack->top == MAX - 1
) to prevent overflow. If not full, it increments thetop
and inserts the value.pop
Function: Removes the top value from the stack. It checks if the stack is empty (stack->top == -1
) to prevent underflow. If not empty, it retrieves the top value, decrementstop
, and returns the value.peek
Function: Returns the value at the top of the stack without removing it. If the stack is empty, it returns'\0'
(null character).
4. Operator Precedence
To determine which operator should be evaluated first, we assign precedence levels:
^
: High precedence (3
).*
and/
: Medium precedence (2
).+
and-
: Low precedence (1
).
int precedence(char operator) { if (operator == ‘^’) return 3; if (operator == ‘*’ || operator == ‘/’) return 2; if (operator == ‘+’ || operator == ‘-‘) return 1; return 0; } |
5. Operator Check
We check if a character is an operator (+, -, *, /, ^
):
int isOperator(char ch) { return (ch == ‘+’ || ch == ‘-‘ || ch == ‘*’ || ch == ‘/’ || ch == ‘^’); } |
6. Converting Infix to Postfix
The function infixToPostfix
performs the conversion step-by-step:
void infixToPostfix(char *infix, char *postfix) { Stack stack; stack.top = -1; // Initialize stack int i, j = 0; for (i = 0; infix[i] != ‘\0’; i++) { if (isalnum(ch)) { // Append remaining operators in the stack to postfix |
7. Main Function
The program takes an infix expression from the user, converts it to postfix, and displays the result:
int main() { char infix[MAX], postfix[MAX]; printf(“Enter an infix expression: “); infixToPostfix(infix, postfix); // Conversion function printf(“Postfix expression: %s\n”, postfix); // Output result return 0; |
This code converts an infix expression (e.g., “A+BC”) to a postfix expression (e.g., “ABC+”) using a stack-based algorithm. It processes the input character by character, appending operands directly to the result and handling operators, parentheses, and precedence using the stack. Remaining operators in the stack are appended to the postfix expression at the end. The main function takes user input, performs the conversion, and displays the result.
Complete Program to Convert Infix to Postfix using Stack in C
#include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <string.h> #define MAX 100 // Stack structure // Stack operations char pop(Stack *stack) { char peek(Stack *stack) { int precedence(char operator) { int isOperator(char ch) { void infixToPostfix(char *infix, char *postfix) { for (i = 0; infix[i] != ‘\0’; i++) { if (isalnum(ch)) { while (stack.top != -1) { postfix[j] = ‘\0’; int main() { printf(“Enter an infix expression: “); infixToPostfix(infix, postfix); printf(“Postfix expression: %s\n”, postfix); return 0; |
Output:
Enter an infix expression: 7+5*3/5^1+(3-2)
Postfix expression: 753*51^/+32-+