Postfix Evaluation In C

Introduction to Postfix Notation:

Postfix notation, also referred to as reverse polish notation, is a mathematical format where operators are positioned after their operands. For instance, the infix expression 3 + 4 can be transcribed in postfix notation as 3 4 +. Correspondingly, the infix expression (2 + 3) 4 can be represented in postfix notation as 2 3 + 4 . This notation offers multiple benefits compared to infix notation. It eradicates the requirement for parentheses, simplifying both the parsing and evaluation processes of expressions.

Postfix Evaluation Algorithm

Postfix evaluation algorithm is a simple algorithm that allows us to evaluate postfix expressions. The algorithm uses a stack to keep track of operands and performs arithmetic operations when an operator is encountered. The algorithm can be summarized in the following steps:

✅ First of all, it will Create an empty stack .
✅ After that, it Scan the expression from left to right .
✅ If an operand is encountered, it push it onto the stack.
✅ If an operator is encountered, pop the top two operands from the stack, perform the operation, and push the result back onto the stack.
✅ After that, it Continue scanning the expression until all tokens have been processed.
✅ When the expression has been fully scanned, the result will be the top element of the stack.

Example:

Let's consider the expression "5 6 7 + * 8 -" . We will evaluate this expression using the postfix evaluation algorithm.

✅ Start scanning the expression from left to right .
✅ Push operand 5 onto the stack.
✅ Push operand 6 onto the stack.
✅ Push operand 7 onto the stack.
✅ Pop operands 7 and 6 from the stack, perform addition, and push the result (13) back onto the stack.
✅ Pop operands 13 and 5 from the stack, perform multiplication, and push the result (65) back onto the stack.
✅ Push operand 8 onto the stack.
✅ Pop operands 8 and 65 from the stack, perform subtraction, and push the result (57) back onto the stack.
✅ The final result is 57 .

Implementation in C:

To execute postfix evaluation in C, it is essential to utilize a stack data structure. An array can serve as the underlying implementation for the stack. Additionally, a top variable is necessary to maintain the position of the topmost element within the stack.

Here is a full C program for evaluating postfix expressions:

Example


#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Stack implementation
int stack[MAX_SIZE];
int top = -1;
void push(int item) {
    if (top >= MAX_SIZE - 1) {
printf("Stack Overflow\n");
        return;
    }
    top++;
    stack[top] = item;
}
int pop() {
    if (top < 0) {
printf("Stack Underflow\n");
        return -1;
    }
    int item = stack[top];
    top--;
    return item;
}
int is_operator(char symbol) {
    if (symbol == '+' || symbol == '-' || symbol == '*' || symbol == '/') {
        return 1;
    }
    return 0;
}
int evaluate(char* expression) {
    int i = 0;
    char symbol = expression[i];
    int operand1, operand2, result;

    while (symbol != '\0') {
        if (symbol >= '0' && symbol <= '9') {
            int num = symbol - '0';
            push(num);
        }
        else if (is_operator(symbol)) {
            operand2 = pop();
            operand1 = pop();
            switch(symbol) {
                case '+': result = operand1 + operand2; break;
                case '-': result = operand1 - operand2; break;
                case '*': result = operand1 * operand2; break;
                case '/': result = operand1 / operand2; break;
            }
            push(result);
        }
i++;
        symbol = expression[i];
    }
    result = pop();
    return result;
}

int main() {
    char expression[] = "5 6 7 + * 8 -";
    int result = evaluate(expression);
printf("Result= %d\n", result);
return 0;
}

Output:

Output


The output of the above program will be:
Result: 57

Explanation:

In the preceding code, we've established the push and pop operations to manage the stack. Additionally, the is_operator function is defined to verify if a character qualifies as an operator. The evaluate function executes the postfix evaluation algorithm.

Within the primary function, we have specified the string "5 6 7 + * 8 -" as an expression. This expression is then provided as input to the evaluate function, which calculates and outputs the result. Subsequently, we display the final result.

Conclusion:

Postfix assessment offers a straightforward and effective method for calculating arithmetic expressions, making use of stacks for smooth implementation. This guide delves into the process of executing postfix assessment in the C programming language with stacks, offering a comprehensive C program for the same purpose.

Introduction to Postfix Notation:

Postfix Evaluation Algorithm

Example:

Implementation in C:

Conclusion:

Input Required