C Program to Evaluate Postfix Expression

Introduction

Postfix expressions, also known as Reverse Polish Notation (RPN), are expressions where the operators follow their operands. Evaluating postfix expressions is straightforward and can be efficiently done using a stack. In this approach, operands are pushed onto the stack, and when an operator is encountered, the required number of operands is popped from the stack, the operation is performed, and the result is pushed back onto the stack.

Example:

• Input: Postfix expression 53+82-*
• Output: Result of the expression -36

Problem Statement

Create a C program that:

• Evaluates a postfix expression using a stack.
• Handles operators like +, -, *, /, and assumes that all operands are single-digit integers.

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 stack array.
3. Implement the Stack Operations:

• Push: Add an element to the stack.
• Pop: Remove and return the top element from the stack.

4. Implement the Postfix Evaluation:

• Iterate over each character of the postfix expression.
• Use the stack to manage operands and calculate the result based on operators.

5. Create a Main Function: Allow the user to input a postfix expression and display the evaluated result.

C Program to Evaluate 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 int stack[MAX]; int top = -1; // Function to push an element onto the stack void push(int value) { if (top >= MAX - 1) { printf("Stack overflow!\n"); return; } stack[++top] = value; } // Function to pop an element from the stack int pop() { if (top < 0) { printf("Stack underflow!\n"); return -1; // Return -1 to indicate an error } return stack[top--]; } // Function to evaluate a postfix expression int evaluatePostfix(char* postfix) { int i = 0; char ch; int operand1, operand2, result; while ((ch = postfix[i++]) != '\0') { if (isdigit(ch)) { // If the character is an operand (digit), push it onto the stack push(ch - '0'); // Convert character to integer } else { // If the character is an operator, pop the top two elements operand2 = pop(); operand1 = pop(); // Perform the operation and push the result back onto the stack switch (ch) { case '+': result = operand1 + operand2; break; case '-': result = operand1 - operand2; break; case '*': result = operand1 * operand2; break; case '/': if (operand2 == 0) { printf("Error: Division by zero!\n"); return -1; // Return -1 to indicate an error } result = operand1 / operand2; break; default: printf("Error: Invalid operator %c\n", ch); return -1; // Return -1 to indicate an error } push(result); // Push the result back onto the stack } } return pop(); // The final result will be the only element left on the stack } int main() { char postfix[MAX]; int result; printf("Enter a postfix expression: "); gets(postfix); // Read the postfix expression from the user result = evaluatePostfix(postfix); // Evaluate the postfix expression if (result != -1) { printf("Result of the postfix expression: %d\n", result); // Display the result } 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 an integer 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 Evaluate a Postfix Expression

• The evaluatePostfix function evaluates a postfix expression by iterating through each character:
  • Operands (digits) are pushed onto the stack.
  • Operators cause the top two operands to be popped, the operation to be performed, and the result to be pushed back onto the stack.
• Finally, the result of the postfix expression is returned by popping the last remaining element from the stack.

Main Function

• The main function reads a postfix expression from the user, evaluates it using the evaluatePostfix function, and displays the result.

Output Example

Example Output:

Enter a postfix expression: 53+82-* Result of the postfix expression: -36 

Conclusion

This C program demonstrates how to evaluate a postfix expression using a stack. It handles basic arithmetic operations and assumes that all operands are single-digit integers. The program is a useful example for understanding stack operations and expression evaluation in C programming.