Skip to main content

Evaluate postfix expression using stack in c

C program for Evaluate postfix expression using stack. Here more information.

// Include header file
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* 
    C program for 
    Evaluate postfix expression
*/
// Stack Node
typedef struct StackNode
{
    // Define useful field of StackNode
    int operand;
    struct StackNode * next;
}StackNode;

StackNode * getStackNode(int operand, StackNode * top)
{
    // Create dynamic memory of StackNode
    StackNode * ref = (StackNode * ) malloc(sizeof(StackNode));
    if (ref == NULL)
    {
        // Failed to create memory 
        return NULL;
    }
    ref->operand = operand;
    ref->next = top;
    return ref;
}
typedef struct MyStack
{
    // Define useful field of MyStack
    struct StackNode * top;
    int count;
}MyStack;

MyStack * getMyStack()
{
    // Create dynamic memory of MyStack
    MyStack * ref = (MyStack * ) malloc(sizeof(MyStack));
    if (ref == NULL)
    {
        // Failed to create memory 
        return NULL;
    }
    ref->top = NULL;
    ref->count = 0;
    return ref;
}
// Returns the number of element in stack
int isSize(MyStack * ref)
{
    return ref->count;
}

int isEmpty(MyStack * ref)
{
    if (isSize(ref) > 0)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}
// Add a new element in stack
void push(MyStack * ref, int value)
{
    // Make a new stack node
    // And set as top
    ref->top = getStackNode(value, ref->top);
    // Increase node value
    ref->count++;
}
// Used to get top element of stack
int peek(MyStack * ref)
{
    if (!isEmpty(ref))
    {
        return ref->top->operand;
    }
    else
    {
        return 0;
    }
}
// Remove a top element 
int pop(MyStack * ref)
{
    int value = peek(ref);
    if (isEmpty(ref) == 0)
    {
        ref->top = ref->top->next;
        // Reduce the size
        ref->count--;
    }
    return value;
}



void evaluate(const char *e)
{
    // Get the length of expression
    int size = strlen(e);
    int a = 0;
    int b = 0;
    MyStack * s = getMyStack();
    int isVaild = 1;
    // work with (+,-,/,*,%) operator
    for (int i = 0; i < size && isVaild; i++)
    {
        if (e[i] >= '0' && e[i] <= '9')
        {
            a = e[i] - '0';
            push(s, a);
        }
        else if (isSize(s) > 1)
        {
            a = pop(s);
            b = pop(s);
            // Perform arithmetic operations between 2 operands
            if (e[i] == '+')
            {
                push(s, b + a);
            }
            else if (e[i] == '-')
            {
                push(s, b - a);
            }
            else if (e[i] == '*')
            {
                push(s, b * a);
            }
            else if (e[i] == '/')
            {
                push(s, b / a);
            }
            else if (e[i] == '%')
            {
                push(s, b % a);
            }
            else
            {
                // When use other operator
                isVaild = 0;
            }
        }
        else if (isSize(s) == 1)
        {
            // Special case  
            // When use +, - at the beginning
            if (e[i] == '-')
            {
                a = pop(s);
                push(s, -a);
            }
            else if (e[i] != '+')
            {
                // When not use  +,-
                isVaild = 0;
            }
        }
        else
        {
            isVaild = 0;
        }
    }
    if (isVaild == 0)
    {
        // Possible case use other operators
        // 1) When using special operators
        // 2) Or expression is invalid
        printf(" Invalid expression %s",e);
        return;
    }
    printf(" %s = %d\n",e, pop(s));
}
int main()
{
    
    // Execute the following expression
    // (1+2)*(3+5)
    evaluate("12+35+*");
    // -((7*2) + (6/2) + 4)
    evaluate("72*62/+4+-");
}

Output

 12+35+* = 24
 72*62/+4+- = -21




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment