Evaluation of Postfix Expression Using Stack in C

In C language, postfix expressions can be evaluated in a variety of ways utilizing a stack.

Some of the most common techniques are listed below:

1. The simplest way for evaluating postfix expressions is the basic stack method: When an operator is encountered, operands are pushed into the stack and popped out. Following the operation on the operands, the outcome is returned to the stack. This procedure continues till the expression's conclusion. The result is then finally removed from the stack, and the stack is then verified to make sure it is empty. Although this approach is straightforward and simple to use, it might not be effective for complex expressions.
2. Recursive Method: In this approach, the postfix expression is assessed using a recursive function. The postfix expression is represented as a string that is sent as input to the function. If an operand is found when scanning the expression from left to right, it is returned by the function. The function is executed recursively with the remainder of the expression as input if an operator is found. Following the operation on the returned operands, the function returns the outcome. The phrase is assessed in its entirety at the end of this procedure. The overhead of function calls might make this technique less efficient even if it may be shorter than the other ways.
3. The Linked List Stack Method: It entails employing a linked list data structure to implement a stack. It entails popping out operand-containing nodes when an operator is met and placing nodes containing operands onto the linked list stack. Following the operation on the operands, the outcome is returned to the stack. This procedure continues till the expression's conclusion. The result is then finally removed from the stack, and the stack is then verified to make sure it is empty. When the size of the stack is unknown beforehand, this approach is very helpful because it is effective for huge expressions.
4. Array stack technique: The array data structure is used to implement a stack in the array stack technique. Although it is similar to the fundamental stack approach, it is more effective since the array's size may be changed dynamically. The top two operands are popped off the stack when an operator is encountered. The operands are placed into the stack as array items. Following the operation on the operands, the outcome is returned to the stack. This procedure continues till the expression's conclusion. The result is then finally removed from the stack, and the stack is then verified to make sure it is empty.
5. Double stack approach: The postfix expression is evaluated using two stacks in the double stack approach. The operands are stored on the first stack, while intermediate results are kept on the second stack. An operand is added to the operand stack whenever it is encountered. The top two operands on the operand stack are popped when an operator is encountered, and they are then used to execute the operation. The outcome is subsequently transferred to the interim result stack. This procedure continues till the expression's conclusion. In order to verify that the stack is empty, the result is then popped off the intermediate result stack. While potentially more effective than the standard stack method, this approach uses more memory.
6. Dynamic stack technique: A dynamically-sized stack that expands and contracts as necessary is used in the dynamic stack technique. A dynamically allocated array is used to implement the stack; it starts off tiny and enlarges as more entries are added to it. If it is important to save memory, the array size is decreased when an element is removed from the stack. As it uses less memory while still allowing quick access to the stack parts, this technique is more memory-efficient than other others. For big expressions, it could not be as effective as other approaches and requires more complicated implementation.
7. Expression Tree Method: Using the postfix expression as a starting point, this method creates an expression tree, which is then traversed to evaluate the expression. The postfix expression is scanned from left to right to build the expression tree, adding a new node for each operand and operator that are found. The operators are used to create new nodes and remove operands from the stack, while the operands are pushed onto the stack. The expression is then evaluated using a post-order traversal after the expression tree has been built. Although this approach is more to put into practice, it can be more effective for big expressions and offers a more adaptable structure for future alterations.
8. Reverse Polish Notation (RPN) Method: This method evaluates expressions in RPN, also known as postfix notation, using a stack. Pushing operands onto the stack entails scanning the expression from left to right. The top two operands are removed from the stack and used to conduct the operation when an operator is encountered. The outcome is then returned to the stack. The final result is popped off the stack when the expression has finished, at which point the operation is complete. The fundamental stack approach is implemented more effectively by the RPN method.

Algorithm for the basic stack approach in C for evaluating postfix expressions uses a stack data structure:

1. Use a struct to define a stack data structure. Use the initialise stack function to initialise the stack.
2. The postfix expression's characters are iterated through.
3. Push any detected digits using the push method into the stack.
4. Use the pop function to remove two operands from the stack if an operator is encountered.
5. Put the operands through the operation, and then store the outcome.
6. Utilize the push method to return the result to the stack.
7. Use the pop method to remove the last result from the stack.
8. Check to see if the stack is empty. The expression is invalid if it is not.
9. Send the outcome back.

Explanation:

This technique evaluates postfix expressions using a stack data structure. Postfix expressions are those in which the operators appear after the operands. For instance, the infix expression "2 + 3" and the expression "2 3 +" are equal.

The algorithm goes through the characters in the postfix expression after initialising a stack with the initialise_stack function. If a digit is found, the push function is used to put it into the stack. If an operator is encountered, the pop function is used to remove two operands off the stack. The operation is then carried out on the operands, and the outcome is pushed using the push function back onto the stack. This procedure continues till the expression's conclusion.

The final result is popped off the stack using the pop function following the loop. The stack's emptiness is then confirmed by the method. The expression is invalid if it is not. The outcome is then given back.

The validity of the postfix expression and the presence of solely single-digit operands as well as the operators +, -, *, and / are presumptions made by this method. It's crucial to keep in mind that this method may be changed to handle expressions with more complicated operators and operands.

Example that uses a stack data structure to evaluate postfix expressions in C:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>


#define MAX_STACK_SIZE 100


// Define stack structure
struct stack {
    int top;
    int items[MAX_STACK_SIZE];
};


// Function to initialize stack
void initialize_stack(struct stack *s) {
    s->top = -1;
}


// Function to check if stack is full
int is_full(struct stack *s) {
    return (s->top == MAX_STACK_SIZE - 1);
}


// Function to check if stack is empty
int is_empty(struct stack *s) {
    return (s->top == -1);
}


// Function to push item onto stack
void push(struct stack *s, int item) {
    if (is_full(s)) {
        printf("Stack is full.\n");
        exit(EXIT_FAILURE);
    }
    s->items[++(s->top)] = item;
}


// Function to pop item from stack
int pop(struct stack *s) {
    if (is_empty(s)) {
        printf("Stack is empty.\n");
        exit(EXIT_FAILURE);
    }
    return s->items[(s->top)--];
}


// Function to evaluate postfix expression
int evaluate_postfix(char *expression) {
    struct stack s;
    initialize_stack(&s);


    int i, operand1, operand2, result;
    char c;


    for (i = 0; expression[i] != '\0'; i++) {
        c = expression[i];


        if (isdigit(c)) {
            push(&s, c - '0');
        } else {
            operand2 = pop(&s);
            operand1 = pop(&s);


            switch (c) {
                case '+':
                    result = operand1 + operand2;
                    break;
                case '-':
                    result = operand1 - operand2;
                    break;
                case '*':
                    result = operand1 * operand2;
                    break;
                case '/':
                    result = operand1 / operand2;
                    break;
                default:
                    printf("Invalid operator.\n");
                    exit(EXIT_FAILURE);
            }


            push(&s, result);
        }
    }


    result = pop(&s);
    if (!is_empty(&s)) {
        printf("Invalid expression.\n");
        exit(EXIT_FAILURE);
    }


    return result;
}


// Driver function
int main() {
    char expression[MAX_STACK_SIZE];
    printf("Enter postfix expression: ");
    scanf("%s", expression);
    int result = evaluate_postfix(expression);
    printf("Result: %d\n", result);
    return 0;
}

Output:

Enter the postfix expression: 23*4+5-
Result: -3

The code uses a struct to define a stack data structure. For operations on the stack, utilise the initialise_stack, is_full, is_empty, push, and pop methods.

Using a stack, the evaluate_postfix method evaluates a postfix expression that is sent to it as a string input. When a digit is found during the function's loop over the expression's characters, the digit is added to the stack. If an operator is found, the result is put back into the stack after the operation, two operands are popped from the stack, and the operation is completed.

By confirming that the stack is empty at the conclusion of the loop, the function additionally looks for expressions that aren't legal. The function returns the expression's outcome.

The main function asks for a postfix expression from the user, runs evaluate_postfix to test it, and outputs the outcome.