C Tutorial

C Tutorial C Language Environment Setup Execution flow of C program C printf and Scanf C Data type C Token Variable in C Operators in C Comments in C Escape Sequence in C C – Storage Classes C Decision control statement Loop Statement in C Break, continue and goto statement in C Type Casting in C Function in C Recursion in C String in C C Array Pointer in C Dynamic memory allocation C –Structure Nested Structure in C Union in C File Handling in C C pre-processor Static Function In C Sizeof In C Selection Sort In C Scope Of Variables In C Runtime Vs Compile Time In C Random Access Lseek In C Queue Implementation In C Pseudo Code In C Prototype In C Pointer To Pointer In C Pointer Arithmetic In C Passing Array To Function In C Null Character In C Merge Sort In C Macros In C Library Functions In C Memory Leak In C Int In C Goto And Labels In C Fibonacci Series In C Fflush In C Derived Data Types In C Data Types In C Const Vs Volatile In C Character Set In C Character Class Tests In C Calloc In C C Pointers Arrays In C Include In C Clrscr In C C Vs Java String Literals In C Types Of Pointers In C Variables In C Volatile In C Why C Is A Middle Level Language Infix To Postfix Program In C Ceil function in C LCM of two numbers in C Quick sort in C Static in C function pointer as argument in C Top Array Keywords in C Add two numbers using the function in C Armstrong program in C using function Array, Declaring Arrays and Array Initialization Limitations of Inline Function in C Merge and Merge sort with example in C Do-While Loop in C For Loop in C While-Loop in C Difference between while and do-while loop in C Array Of Structures in C Data Structures And Algorithms in C Types Of Structures In C How to Avoid Structure Padding in C Use of Structure in C Do WHILE LOOP in C Programming Examples For Loop in C Programming Examples Entry Control Loop in C Exit control loop in C Infinite loop in C Nested loop in C pow() function in C String Handling functions in C Prime Number code in C Factorial Program in C using For Loop Factorial Program in C Using While Loop Fibonacci Series in C Using For Loop Fibonacci series in C using while loop Prime Number Program in C using for Loop While Loop in C programming examples Built-in functions in C Assert() Function C vs Java Strings Call Back Function in Embedded C Else If Ladder fgets() function Ftell() Function getc() function getch() function gets() function Heap Sort Nested if-else statement Pi() Function Positioning of file Write() function abs() function in C Attributes in C C program to find factorial of a number using Recursion Ferror() in c fopen() function in C Fibonacci series program in C using Recursion Formatted Input and output function in C Snake Game in C User Defined Functions in C Beep() function in C Cbrt() function in C Hook() function in C Isalnum() function in C C Program to find the Roots of a Quadratic Equation C Switch Statements Difference between rand() and srand() function in C Difference between while and for loop in C Doubly Linked list in C Example of Iteration in C How to use atoi() function in C How to use floor() function in C How to use sine() function in C How to use Typedef Struct in C Integer Promotions in C C Program Swap Numbers in cyclic order Using Call by Reference C Program to Find Largest Number Using Dynamic Memory Allocation C Program to Find the Largest Number using Ternary Operator C/C++ Program to Find the Size of int, float, double and char Find the Largest Three Distinct Elements in an Array using C/C++ Loop Questions in C Modulus on Negative Numbers in C Multiplication table program in C using For loop Nested Loops in C Programming Examples C Program for Mean and Median of an Unsorted Array Results of Comparison Operations in C and C++ Reverse a Stack using Recursion in C Simple hash() function in C strcat() Function in C Sum of N numbers in C using For loop Use of free() function in C Write a program that produces different results in C and C++ C Function Argument and Return Values Keywords in C Bank management system in C Calendar application in C Floor() Function in C Free() Function in C How to delete a file in C How to move a text in C Remove an element from an array in C Unformatted input() and output() function in C What are linker and loader in C SJF Scheduling Program in C Socket Programming in C Structure in C Tower of Hanoi in C Union Program in C Variable Declaration in C What is Linked List in C While Loop Syntax in C fork() in C GCD program in C Branching Statements in C Comma Operator in C Control statement in C Double Specifier in C How to create a binary file in C Long int in C Palindrome Number in C Pure Virtual Function in C Run Time Polymorphism in C Types of Array in C Types of Function in C What is a buffer in C What is required in each C Program Associativity of Operators in C Bit Stuffing Program in C Actual and Formal Parameters Addition of two Numbers in C Advantages of function in C Arithmetic Progression Program in C Binomial Coefficient Program in C Difference between Array and List in C Diffie-Hellman Algorithm in C How to convert a number to words in C How to convert a string to hexadecimal in C Difference between If and Switch Statement in C C and C++ Binary Files C program that does not Suspend when Ctrl+Z is Pressed Different ways to Declare the Variable as Constant in C Range of Int in C C Program to find the size of a File FIFO Example in the C Language For loop in C Programming GCD program of two numbers in C GPA Calculator in C How to Calculate Time Complexity in C How to include graphics.h in C How to measure time taken by a function in C How to return a Pointer from a Function in C What is the main in C Addition of Matrix in C Booleans in C C Program for Extended Euclidean algorithms C Program of Fencing the Ground Ceil and Floor in C Compound Interest Program in C Displaying Array in C Distance Vector Routing Protocol Program in c Dos.h Header File in C Language DSA Program in C Explain the two-way selection in C Fee Management System in C File Operations in C Malloc function in C Multiplication Table in C Simple Programs in C Language tolower() Function in C Type Conversion in the C Why does sizeof(x++) not Increment x in C Advantages of Dynamic Memory Allocation in C Armstrong Number in C Assignment Operator Program in C Banker’s Algorithm in C Binary Search in C with Best and Worst Time Complexity Caesar Cipher Program in C Call by Value and Call by Reference in C Conditional Operator in C CRC Program in C Deadlock Detection Program in C Decimal to Binary in C Difference between If Else and Nested If Else in C Difference between Pre-increment and Post-increment in C Difference between Scope and Lifetime in C Evaluation of Arithmetic Expression in C Explain the Increment and Decrement Operators in C Fseek Function in C Functions in C How to Find Square Free Numbers in C Length of an Array Function in C OpenGL in C Projects on C language in 2023 Purpose of a Function Prototype in C Stdio.h in C Two-Dimensional array in C What is String Comparison in C C Compilers for Windows Functions and Recursion in C How to Declare Boolean in C How to Declare Character in C How to Round up a number in C How to use strlen() in C Pointer Declaration in C Algorithm for String Palindrome in C C Program to find ASCII value of a character Constant Pointer in C How to find string length in C using strlen() function Implicit and Explicit in C Indirect Recursion in C Input and Output functions in C isupper() in C Jump Statement in C Lifetime of a Variable in C Linker Error in C Language Numeric Constant in C Size of Pointer in C Square Root in C Language Static and Dynamic Memory allocation String Declaration in C Strong Number in C Symmetric Matrix in C Types of C Tokens What is a Size of Pointer in C What is Increment and Decrement Operator in C 1 2 3 4 Series Program in C Advantages and Disadvantages of C Language C Program for Polynomial Addition C Program to Count the Number of Vowels in a String C Programming Errors and Solutions Compilation Errors in C Complex C Programs Difference between Argument and Parameter in C Difference between char s[] and char *s in C Evaluation of Postfix Expression Using Stack in C Find Leftmost and Rightmost Set Bit of a Number fprintf and fscanf in C Introduction to Dynamic Array in C Print Address in C Realloc function in C Ternary Operators in C Types of Tokens in C with Examples Difference between Static and Dynamic Memory Allocation in C Addition Program in C Array Definition in C Array of Pointers in C Arrow Operator in C Average of Two Numbers in C Binary to Decimal in C Binary to Octal in C BREAK STATEMENT in C C Programming Operators Questions C Programs Asked in Interview Calculator Program in C C Program to Read and Print an Employee's Detail Using Structure Bubble Sort Algorithm in C C Program to Find Area and Perimeter of Circle C Program to Check Whether a Given Number is Even or Odd C in Roman Numerals C Program to Make a Simple Calculator Using Switch Case Insertion Sort Program in C How to take input in string in C GCC Conflicting Types in C Function Definition in C Format Specifier for Hexadecimal in C Flowchart in C Float in C Fizzbuzz Implementation in C Conditional Statement in C Conio.h functions list in C Constants in C Dynamic Array in C Decision Making Statements in C Continue Statement in C Creation of Thread in C DFS Algorithm in C Difference between parameter and arguments in C Dijkstra's Algorithm in C Leap Year Program in C Jump Statements in C Modulus Operator in C Memory Allocation in C Simple Interest Program in C Reverse Array in C Recursive Function in C Queue in C Printing Pascal’s Triangle in C Preprocessor Directives in C Perror() in C Perfect Number in C Programming Language Parameter Passing Techniques in C Pascal Triangle in C Patterm Program in C Diagonal Matrix in C Converting Dollars into Rupees in C Typedef Function Pointer in C Unsigned Char in C C Program to Calculate Percentage C Program to Find Sum of Array Elements Clock Program in C How to reverse a number in C? Insert Array in C Kbhit() Function in C Can We Learn Python Without C? C program to convert decimal to hexadecimal C program to draw a circle C Program to Calculate Electricity Bill C program for string concatenation C program to convert decimal to binary without using array Graphics Programming in C File Handling Functions in C Convert Char to Int in C Identifiers In C ftok() function in C Dangling else program in C DFS Program in C Ifdef in C How to initialise an array in c Implementation of queue using Array in C Selection Statements in C Size of Char in C Strchr() function in C Symbolic Constants in C Tree Data Structure in C Type Conversion in C Types of Constants in C Void data type in C Argument in C Bitwise Operator in C Circular queue in C COMPILER IN C ctype h in c execvp() function in C Exit function in C Hashing in C How to define a global variable in C

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.