Create FREE 'HowTo' Videos with MyGuide

Stack



Pass Quiz and Get a Badge of Learning



Content "filtered", Please subscribe for FULL access.


Chapter 3 : Stack

Topics covered in this snack-sized chapter:


Stack arrow_upward


  • A Stack is a linear data structure.
  • It is an ordered list in which addition of a new data element or deletion of an already existing data element is performed at same end.
  • It is also called Last in First out (LIFO) data structure.
  • Stack can be used to reverse a sequence.
  • For example, if a string ”Computers” is entered by the user the stack can be used to create and display the reverse string “sretupmoC” as follows.
  • The program simply pushes all of the characters of the string into the stack. Then it pops and display until the stack is empty.

  • Stack Categorization arrow_upward


  • Stack is characterized by two fundamental operations:
    • Push
    • Pop

    Push:

  • Adds an item to the top of the stack or initializing the stack if it is empty.

  • Pop:

  • Removes an item from the top of the stack and return its value or results in an empty stack.
  • Every stack has a fixed location in memory at which it begins.
  • Infix to Postfix Conversion arrow_upward


  • Scan the Infix expression left to right.
  • If the character x is an operand:
    • Output the character into the Postfix Expression.
  • If the character x is a left or right parenthesis:
    • If the character is ‘(‘ then Push it into the stack.
    • If the character is ‘)’ then repeatedly pop and output all the operators/characters until ‘(‘ is popped from the stack.
  • If the character x is a regular operator then follow the below steps:
    • Check the character y currently at the top of the stack.
    • If Stack is empty or y=‘(‘ or y is an operator of lower precedence than x, then push x into stack.
    • If y is an operator of higher or equal precedence than x, then pop and output y and push x into the stack.
  • When all characters in infix expression are processed repeatedly pop the character(s) from the stack and output them until the stack is empty.
  • #include<stdio.h>
    #include<stdlib.h>
    #define STACKSIZE 20
    typedef struct{
    int top;
    char items[STACKSIZE];
    }STACK;
    void push(STACK *, char);
    char pop(STACK *);
    void main()
    {
    int i;
    char x,y, E[20] ; /* Assume that Infix Expression E contains single-digit integers/parenthesis/operators*/
    STACK s;
    s.top = -1; /* Initialize the stack is */
    printf("Enter the Infix Expression:");
    scanf("%s",E);
    printf("Postfix Expression is:");
    for(i=0;E[i] != '\0';i++){
    x= E[i];
    if(x<='z' && x>='a') /* Consider all lowercase letter operands from a to z */
    printf("%c",x);
    else if(x == '(')
    push(&s ,x);
    else if(x == ')'){
    y=pop(&s) ;
    while(y != '('){
    printf("%c",y);
    y=pop(&s);
    }
    }
    else {
    if(s.top ==-1 || s.items[s.top] == '(')
    push(&s ,x);
    else {
    y = s.items[s.top]; /* y is the top operator in the stack*/
    if( y=='*' || y=='/'){ /* precedence of y is higher/equal to x*/
    printf("%c", pop(&s));
    push(&s ,x);
    }
    else if ( y=='+' || y=='-')
    if( x=='+' || x=='-') { /* precedence of y is equal to x*/
    printf("%c",pop(&s));
    push(&s ,x);
    }
    else /* precedence of y is less than x*/
    push(&s ,x);
    }
    }
    }
    while(s.top != -1)
    printf("%c",pop(&s));
    getch();
    }
    void push(STACK *sptr, char ps) /*pushes ps into stack*/
    {
    if(sptr->top == STACKSIZE-1){
    printf("Stack is full\n");
    exit(1); /*exit from the function*/
    }
    else
    sptr->items[++sptr->top]= ps;
    }
    char pop(STACK *sptr)
    {
    if(sptr->top == -1){
    return 0;
    exit(1); /*exit from the function*/
    }
    else
    return sptr->items[sptr->top--];
    }
    
    OUTPUT:
    Enter the Infix Expression:(a+b-c)*d-(e+f)
    Postfix Expression is:ab+c-d*ef+-
    

    Thank You from Kimavi arrow_upward


  • Please email us at Admin@Kimavi.com and help us improve this tutorial.


  • Mark as Complete => Receive a Certificate in Data-Structure


    Kimavi Logo

    Terms and conditions, privacy and cookie policy | Facebook | YouTube | TheCodex.Me | Email Kimavi


    Kimavi - A Video Learning Library { Learning is Earning }

    Get Ad Free Learning with Progress Report, Tutor Help, and Certificate of Learning for only $10 a month



    All videos on this site created using MyGuide.

    Create FREE HowTo videos with MyGuide.